自动搬运

查看原文

来自洛谷，原作者为

	Monster_Qi **

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

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

以下是正文

直接跑无向图最大团洛谷上能得70分，惊了。说说正解，首先A国的必须xor后mod2余1，就相当于两个人必须是1奇1偶，所以A国的人只能选0,1,2个，我们可以暴力枚举选谁。继续考虑B国，现在的问题实际上就简化为了在B国中选出一个最大团，这个团也必须和A国所选出的人是朋友，又因为最大团=总点数-补图的最大匹配，补图就是将原来连着的边断了，原来没连的边连上，而进一步可以发现其实B国的补图是一个二分图，左部点是%2余1的，右部点是%2余0的，如果它们或起来有偶数个1就可以连边，然后就是二分图中求一个最大匹配，我用的匈牙利卡了过去。。好像这道题特殊数据可以卡死匈牙利，哪位大佬有扔一个谢谢了。 码风应该是比较正常的。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

using namespace std;
const int MAXN = 3205;
const int MAXM = 1500*1500+5;

inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f?x:-x;
}

int T,A,B,M,head[MAXM],cnt,ans;
int to[MAXM],nxt[MAXM],now;
int a[MAXN],b[MAXN],e[MAXN][MAXN];
int num,t,vis[MAXN],flag[MAXN],match[MAXN];

inline void add(int bg,int ed){
	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}

inline bool dfs(int x){
	for(register int i=head[x];i;i=nxt[i]){
		int u=to[i];
		if(vis[u]!=num && flag[u]==t){
			vis[u]=num;
			if(!match[u] || dfs(match[u])){
				match[u]=x;
				return true;
			}
		}
	}
	return false;
}

int main(){
	T=rd(); 
	A=rd();B=rd();M=rd();
	for(register int i=1;i<=A;i++) a[i]=rd();
	for(register int i=1;i<=B;i++) b[i]=rd();
	for(register int i=1;i<=B;i++)if((b[i]&1)) //建补图。 
		for(register int j=1;j<=B;j++) 
			if(!(b[j]&1) && !((__builtin_popcount((b[i]|b[j])))&1)) add(i,j);
				//__builtin_popcount 查询二进制下1的个数，偷了个懒，联赛最好不要用吧。。 
	for(register int i=1;i<=M;i++) {
		int x=rd(),y=rd();
		e[x][y+A]=e[y+A][x]=1;
	}
	for(register int i=1;i<=B;i++)if((b[i]&1)){  //A中的点都不选。 
		num++;
		if(dfs(i)) ans++;
 	}ans=B-ans;  //最大团=总点数-补图的最大匹配。 
	for(register int i=1;i<=A;i++){   //枚举A中选1个点 
		t++;int sum=0;now=0;
		memset(match,0,sizeof(match));
		for(register int j=1;j<=B;j++)
			if(e[i][j+A]) flag[j]=t,now++; //记录有几个点在子图里 
		for(register int j=1;j<=B;j++)
			if(flag[j]==t && (b[j]&1)) {
				num++;  //不memset,时间戳 
				if(dfs(j)) sum++; 
			}
		ans=max(ans,now-sum+1); //加上A中的那个点 
	}
	for(register int i=1;i<=A;i++) //枚举A中选2个点 
		for(register int j=i+1;j<=A;j++)if((a[i]^a[j])&1){
			memset(match,0,sizeof(match));
			t++;int sum=0;now=0;
			for(register int k=1;k<=B;k++)
				if(e[i][k+A] && e[j][k+A]) flag[k]=t,now++;
			for(register int k=1;k<=B;k++)
				if(flag[k]==t && (b[k]&1)) {
					num++;
					if(dfs(k)) sum++;
				}
			ans=max(ans,now-sum+2); //加上A中那两个点 
		}
	cout<<ans<<endl;
	return 0;
}