histcat @ 2023-10-31 21:49:28
rt，感谢 https://www.luogu.com.cn/record/132684651
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int G[N][N];
int n;
vector <int> g[N];
int color[N];
vector <int> block[N][5];
int bcnt;
bool f[N][N];//能否在前i个连通块内 在A组中放入j个人
int path[N][N];
int belong[N];
int main()
{
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
int k;
for(int i = 1;i <= n;i++)
{
while(1)
{
cin >> k;
if(k != 0)
{
G[i][k] = 1;
}
else
{
break;
}
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(i == j) continue;
if(G[i][j] == 0 || G[j][i] == 0)
{
g[i].emplace_back(j);
}
}
}
function<void(int, int)> bfs = [&](int be, int star)
{
color[be] = 1;
queue <int> qwq;
qwq.push(be);
while(qwq.size())
{
int t = qwq.front();
block[bcnt][color[t]].emplace_back(t);
qwq.pop();
for(auto v : g[t])
{
if(color[v] != 0)
{
if(color[v] == color[t])
{
cout << "No solution";
exit(0);
}
else
{
continue;
}
}
else
{
color[v] = 3 - color[t];
qwq.push(v);
}
}
}
};
for(int i = 1;i <= n;i++)
{
if(color[i] == 0)
{
bcnt++;
bfs(i, bcnt);
}
}
f[0][0] = 1;
for(int i = 1;i <= bcnt;i++)
{
for(int j = 1;j <= (n >> 1);j++)
{
if(path[i][j]) continue;
if(j - block[i][1].size() >= 0 && f[i - 1][j - block[i][1].size()])
{
f[i][j] = 1;
path[i][j] = 1;
}
if(j - block[i][2].size() >= 0 && f[i - 1][j - block[i][2].size()])
{
f[i][j] = 1;
path[i][j] = 2;
}
}
}
int ans = 0x3f3f3f3f;
int q = 0;
for(int i = 1;i <= (n >> 1);i++)
{
if(f[bcnt][i])
{
if(n - 2 * i < ans)
{
ans = n - 2 * i;
q = i;
}
}
}
// cout << ans << "\n";
// vector aannss<int> qwq;
function<void(int, int)> print = [&](int i, int j)
{
if(i == 0) return;
print(i - 1, j - block[i][path[i][j]].size());
for(auto t : block[i][path[i][j]])
{
belong[t] = 1;
}
};
print(bcnt, q);
cout << q << " ";
for(int i = 1;i <= n;i++)
{
if(belong[i] == 1) cout << i << " ";
}
cout << "\n";
cout << n - q << " ";
for(int i = 1;i <= n;i++)
{
if(belong[i] == 0) cout << i << " ";
}
// cout << ans;
return 0;
}by 123huchenghao @ 2024-06-29 20:48:55
#include <bits/stdc++.h>
using namespace std;
const int MN=105;
const int MM=105;
typedef long long ll;
bool g[MN][MN],f[MN][MN];
int n,num[MM][2],pre[MN][MN],ans;
vector<int> cont[MN][2];
int mtc[MN],sum=0;
void dfs(int x,int fa,int col)
{
num[sum][mtc[x]=col]++;cont[sum][col].push_back(x);
for (int i=1;i<=n;++i)
if (!g[i][x] && i!=fa && x!=i)
{
if (mtc[i]==-1) dfs(i,x,col^1);
else if (mtc[i]==col) {printf("No solution");exit(0);}
}
}
void dp()
{
f[0][0]=true; //as a beginner.
for (int i=1;i<=sum;++i)
for (int j=0;j<=n/2;++j)
{
int t=j-num[i][0];
//what can be carried must be the best one.
if (t>=0&&f[i-1][t]) f[i][j]=true,pre[i][j]=0;
t=j-num[i][1];
if (t>=0&&f[i-1][t]) f[i][j]=true,pre[i][j]=1;
}
for (int i=n/2;i>=0;--i) if (f[sum][i]) {ans=i;break;}
}
void print()
{
int res[MN]={0},t=ans;
bool p[MN]={false};
for (int i=sum;i>0;--i)
{
for (int j=0;j<cont[i][pre[i][t]].size();++j) p[res[++res[0]]=cont[i][pre[i][t]][j]]=true;
t-=num[i][pre[i][t]];
}
sort(res+1,res+res[0]+1);
printf("%d ",res[0]);for (int i=1;i<=res[0];++i) printf("%d ",res[i]);
printf("\n%d ",n-res[0]);for (int i=1;i<=n;++i) if (!p[i]) printf("%d ",i);
}
ll read(){
ll f=1,x=0;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
n=read();
int m,v;
for (int i=1;i<=n;++i)
{
v=-1;
while (v!=0){v=read();g[i][v]=true;}
}
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j)
{
if (!(g[i][j]&&g[j][i]) && (g[i][j]||g[j][i])) g[i][j]=g[j][i]=false;
}
memset(mtc,-1,sizeof(mtc));
for (int i=1;i<=n;++i)
if (mtc[i]==-1)
{
sum++;
dfs(i,0,1);
}
dp();
print();
return 0;
}