题解 P2423 【[HEOI2012]朋友圈】
Monster_Qi
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就可以连边，然后就是二分图中求一个最大匹配，我用的匈牙利卡了过去。。好像这道题特殊数据可以卡死匈牙利，哪位大佬有扔一个谢谢了。
码风应该是比较正常的。
## 代码
```cpp
#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;
}
```