bzoj 2744: [HEOI2012]朋友圈网络流

2019-11-08 00:52:29

字体：大中小

来源：转载

供稿：网友

题意

在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述： 1. A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，那么这两个人都是朋友，否则不是； 2. B国：每个人都有一个友善值，当两个B国人的友善值a、b，如果a xor b mod 2=0 或者 (a or b)化成二进制有奇数个1，那么两个人是朋友，否则不是朋友； 3. A、B两国之间的人也有可能是朋友，数据中将会给出A、B之间“朋友”的情况。 4. 在AB两国，朋友圈的定义：一个朋友圈集合S，满足 S∈A∪ B ，对于所有的i，j∈ S ，i 和 j 是朋友由于落后的古代，没有电脑这个也就成了每年最大的难题，而你能帮他们求出最大朋友圈的人数吗？ A<=200,B<=3000

分析

可以从题目得到一些有用的信息：A国中最多只能选两个人；B国的人被分成两部分，每部分都是完全图，两部分之间有一些连边；要求一个最大的团。我就是分析到这一步然后就不会了。。。显然一个图的最大团等于其反图的最大独立集，那么我们就把B国的反图建立出来，显然这是一个二分图。然后我们枚举在A中选择哪一个或两个人，再在B中跑最大独立集即可。一次AC。

代码

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<queue>#define N 3005#define inf 0x3f3f3f3fusing namespace std;int cnt,cntnow,A,B,m,s,t,dis[N],use[N],last[N],ls[N],cur[N],ans,a[N],b[N];struct edge{int to,next,c;}e[N*N];queue <int> q;void addedge1(int u,int v){ e[++cnt].to=v;e[cnt].next=ls[u];ls[u]=cnt; ++cnt;}void addedge(int u,int v,int c){ e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt;}void clear(){ for (int i=cntnow;i<=cnt;i+=2) { e[i].c=1;e[i^1].c=0; }}int count(int x){ int ans=0; while (x) { ans++; x-=x&(-x); } return ans;}bool bfs(){ for (int i=s;i<=t;i++) dis[i]=0; dis[s]=1; while (!q.empty()) q.pop(); q.push(s); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=last[u];i;i=e[i].next) if (use[e[i].to]&&e[i].c&&!dis[e[i].to]) { dis[e[i].to]=dis[u]+1; if (e[i].to==t) return 1; q.push(e[i].to); } } return 0;}int dfs(int x,int maxf){ if (x==t||!maxf) return maxf; int ret=0; for (int &i=cur[x];i;i=e[i].next) if (use[e[i].to]&&e[i].c&&dis[e[i].to]==dis[x]+1) { int f=dfs(e[i].to,min(e[i].c,maxf-ret)); ret+=f; e[i].c-=f; e[i^1].c+=f; if (ret==maxf) break; } return ret;}void dinic(){ while (bfs()) { for (int i=s;i<=t;i++) cur[i]=last[i]; ans+=dfs(s,inf); }}int main(){ scanf("%d%d%d",&A,&B,&m); for (int i=1;i<=A;i++) scanf("%d",&a[i]); for (int i=1;i<=B;i++) scanf("%d",&b[i]); cnt=1; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); addedge1(x,y); } cntnow=cnt+1; for (int i=1;i<=B;i++) if ((b[i]&1)==0) for (int j=1;j<=B;j++) if ((b[j]&1)==1&&count(b[i]|b[j])%2==0) addedge(i,j,1); s=0;t=B+1; for (int i=1;i<=B;i++) if ((b[i]&1)==0) addedge(s,i,1); else addedge(i,t,1); for (int i=s;i<=t;i++) use[i]=1; dinic(); for (int i=1;i<=B;i++) use[i]=0; int mx=B-ans; for (int i=1;i<=A;i++) { int tot=0; for (int j=ls[i];j;j=e[j].next) { use[e[j].to]=1;tot++; } ans=0;clear(); dinic(); mx=max(mx,tot-ans+1); for (int j=ls[i];j;j=e[j].next) use[e[j].to]=0; } for (int i=1;i<A;i++) for (int j=i+1;j<=A;j++) if ((a[i]^a[j])%2==1) { for (int k=ls[i];k;k=e[k].next) use[e[k].to]++; for (int k=ls[j];k;k=e[k].next) use[e[k].to]++; int tot=0; for (int k=1;k<=B;k++) if (use[k]) { use[k]--; if (use[k]) tot++; } clear();ans=0; dinic(); mx=max(mx,tot-ans+2); for (int k=ls[i];k;k=e[k].next) use[e[k].to]=0; } PRintf("%d",mx); return 0;}

上一篇：310. Minimum Height Trees

下一篇：Eclipse安装maven插件