二分图【洛谷P2175】 小Z的游戏分队

二分图【洛谷P2175】 小Z的游戏分队

P2175 小Z的游戏分队

小Z受不了寂寞，准备举办一次DOTA比赛，为了能让ACM班全部都参加比赛，他还特制了一张DOTA地图能够支持任意多人打任意多人。

现在问题来了，怎么把这么多人分成两队？小Z的想法是，每个人报上自己愿意同队的同学，接着小Z会按如下要求将所有人分为两队：

对任意同学甲，和同学甲同队的人，必须都是同学甲愿意同队的同学。

小Z希望两队的人数差尽量小，如果这种分组不存在，那么输出No solution。

先想判无解的情况。

因为分两个组，所以可以通过二分图染色判环。

那么按照不认识关系建边。

（我也不知道为什么想到了按照不认识的关系建边，可能是因为样例给的认识的太多我画不出那个图，喵喵喵~~)

然后因为可能会存在多个环，需要处理一下，统计每个环内两个颜色点分别的个数。

实测第9,10个点卡多个环。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>using namespace std;inline int read(){int sum=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}return sum*f;
}const int wx=3000;int flag[wx][wx];
int num;
int n,tot;
int sjc[wx],zmj[wx][wx];
int head[wx],col[wx],in[wx],ed[wx],vis[wx],size[wx];struct e{int nxt,to;
}edge[wx*wx];void add(int from,int to){edge[++num].nxt=head[from];edge[num].to=to;head[from]=num;
}queue<int > q;bool bfs(){for(int i=1;i<=n;i++){if(!ed[vis[i]]&&size[vis[i]]>1){ed[vis[i]]=1;col[i]=1;q.push(i);}}while(q.size()){int u=q.front(); q.pop();for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(col[v]==col[u])return false;if(col[v])continue;else {col[v]=3-col[u];q.push(v);}}}return true;
}void dfs(int u){size[vis[u]]++;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(vis[v])continue;vis[v]=vis[u];dfs(v);}
}void dfs2(int u){zmj[vis[u]][col[u]]++; sjc[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(vis[v]!=vis[u]||sjc[v])continue;dfs2(v);}
}int main(){n=read();for(int i=1;i<=n;i++){while(1){int x; x=read();if(!x)break;flag[i][x]=1;}for(int j=1;j<=n;j++){if(i!=j&&!flag[i][j]){add(i,j); add(j,i);
//              cout<<i<<" "<<j<<endl;in[j]++; in[i]++;}}}for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=++tot;dfs(i);}}if(!bfs())printf("No solutionn");else{int ans1=0,ans2=0;memset(ed,0,sizeof ed);for(int i=1;i<=n;i++){if(!ed[vis[i]]&&size[vis[i]]>1){ed[vis[i]]=1;dfs2(i);}}for(int i=1;i<=tot;i++){if(size[i]==1){if(ans1>ans2)ans2++;else ans1++;}else {if(ans1>ans2)ans2+=max(zmj[i][1],zmj[i][2]),ans1+=min(zmj[i][1],zmj[i][2]);else ans1+=max(zmj[i][1],zmj[i][2]),ans2+=min(zmj[i][1],zmj[i][2]);}}printf("%d %dn",min(ans1,ans2),max(ans1,ans2));}
//  for(int i=1;i<=n;i++)printf("%d %dn",i,col[i]);return 0;
}

转载于:.html