hdu 3081(二分+最大流+并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3081

思路设源点为0，汇点为2*n+1,对没吵过架的女生和男生连容量为1的边（这里要用到并查集，每个女生的朋友也可以和该男生连边），然后就是源点与女生连边，容量为mid(0<=mid<=n),男生与汇点也连容量为mid的边(这里的mid即为为每个男孩和女孩找到了k个不同的伴侣，说明游戏可以进行k轮,附上链接：http://blog.csdn.net/qq564690377/article/details/7857983），然后就是二分搜索了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 222
#define inf 1<<30
int map[MAXN][MAXN];
int mm[MAXN][MAXN];
int pre[MAXN];
int level[MAXN];
int gap[MAXN];
int parent[MAXN];
int NV,n,m,f;

void Initiate(){
    for(int i=1;i<=2*n;i++){
        parent[i]=-1;
    }
}

int Find(int x){
    int s;
    for(s=x;parent[s]>0;s=parent[s])
        ;
    while(x!=s){
        int tmp=parent[x];
        parent[x]=s;
        x=tmp;
    }
    return s;
}

void Union(int u,int v){
    int r1=Find(u);
    int r2=Find(v);
    if(r1==r2)return ;
    if(parent[r1]>parent[r2]){
        parent[r2]+=parent[r1];
        parent[r1]=r2;
    }else {
        parent[r1]+=parent[r2];
        parent[r2]=r1;
    }
}


int SAP(int vs,int vt){
    memset(pre,-1,sizeof(pre));
    memset(level,0,sizeof(level));
    memset(gap,0,sizeof(gap));
    int v,u=pre[vs]=vs,maxflow=0,aug=inf;
    gap[0]=NV;
    while(level[vs]<NV){
        for(v=1;v<=vt;v++){
            if(map[u][v]&&level[u]==level[v]+1){
                break;
            }
        }
        if(v<=vt){
            pre[v]=u;
            u=v;
            if(v==vt){
                aug=inf;
                for(int i=v;i!=vs;i=pre[i]){
                    if(aug>map[pre[i]][i])aug=map[pre[i]][i];
                }
                maxflow+=aug;
                for(int i=v;i!=vs;i=pre[i]){
                    map[pre[i]][i]-=aug;
                    map[i][pre[i]]+=aug;
                }
                u=vs;
            }
        }else {
            int minlevel=NV;
            for(int v=1;v<=vt;v++){
                if(map[u][v]&&minlevel>level[v]){
                    minlevel=level[v];
                }
            }
            gap[level[u]]--;
            if(gap[level[u]]==0)break;
            level[u]=minlevel+1;
            gap[level[u]]++;
            u=pre[u];
        }
    }
    return maxflow;
}

void Build(int k){
    memset(map,0,sizeof(map));
    for(int i=1;i<=n;i++){
        map[0][i]=k;
        map[i+n][2*n+1]=k;
    }
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=2*n;j++){
            map[i][j]=mm[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(Find(i)==Find(j)){
                for(int k=n+1;k<=2*n;k++){
                    if(map[i][k])map[j][k]=1;
                }
            }
        }
    }
}


int Binary_Search(){
    int low=0,high=n,tmp;
    NV=2*n+2;
    while(low<=high){
        int mid=(low+high)/2;
        Build(mid);
        if(mid*n==SAP(0,2*n+1)){
            tmp=mid;//这里需要保留mid值。
            low=mid+1;
        }else 
            high=mid-1;
    }
    return tmp;
}


int main(){
    int _case,g,b,g1,g2;
    scanf("%d",&_case);
    while(_case--){
        scanf("%d%d%d",&n,&m,&f);
        Initiate();
        memset(map,0,sizeof(map));
        memset(mm,0,sizeof(mm));
        for(int i=1;i<=m;i++){
            scanf("%d%d",&g,&b);
            map[g][b+n]=1;
            mm[g][b+n]=1;//保留原图，因为每次SAP之后，图就改变了。
        }
        for(int i=1;i<=f;i++){
            scanf("%d%d",&g1,&g2);
            if(Find(g1)!=Find(g2)){
                Union(g1,g2);
            }
        }
        int ans=Binary_Search();
        printf("%d\n",ans);
    }
    return 0;
}