题解 P1285 【队员分组】
思路:
- 首先这是一个存在性的01背包问题。分成两组联系到二分图上。
- 逻辑上有：两个不是互相认识的话必然存在于互相排斥的两组。对这些有排斥作用的，即有联系的点放在一张图上，在新的图上跑二分图染色，就可以实现分组了。
具体：
f[i][j]表示的意思是，使用前i个联通块里的0或是1的染色点是否能达到j的容量。
f[i][j]=f[i][j-num[i][0]],j>=num[i][0]
f[i][j]=f[i][j-num[i][1]],j>=num[i][1]数一下联通块个数，当作是01背包的个数。取染色为0的或者染色为1的背包都是可行的。记录路径pre[i][j]。结果要在f[blo_sum][j]找j(1<=j<=2/n)最大的一个。
无解情况：在染色的时候判断是否矛盾，即非二分图。
其他：
- 注意补图的概念。
- 为什么要求联通块这个东西呢？因为不同块之间的元素是互不影响的，即不同块的元素之间组别怎么分都是任意的。
- 建补图的过程中要注意：有单向认识的边逻辑上都是认为不能在同一组的，所以要把这种边当作是两两都不认识的边。否则染色的dfs就不好控制了。这里还花了好多时间去调试呢。
- 这道题原题是POJ1112。还得抱怨一句这里的数据太水了。
#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;
}