二分图【洛谷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 solution\n");
    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 %d\n",min(ans1,ans2),max(ans1,ans2));
    }
//  for(int i=1;i<=n;i++)printf("%d %d\n",i,col[i]);
    return 0;
}

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

原文：https://www.cnblogs.com/wangxiaodai/p/9866264.html