自动搬运

查看原文

来自洛谷，原作者为

	iyanhang **

搬运于2025-08-24 21:23:20，当前版本为作者最后更新于2018-04-07 23:00:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路:

• 首先这是一个存在性的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;
}