Marriage Match III

1
4 5 1 2
1 1
2 3
3 2
4 2
4 4
1 4
2 3

3
这道题和hdu 3081差不多，只不过在原题意上多了一条（女孩可一与k个任意男孩(也许吵架)相连），因此解决方法也可以在原基础上加工。
推荐一篇hdu 3081的博客，链接：http://blog.csdn.net/qq564690377/article/details/7857983
分析：将女孩拆点（v1，v2）用并查集将女孩之间的关系连接起来，再在此基础上将v1与所有关系（直接和间接）的男孩连接，
v2与所有没关系的男孩连接，v1，v2之间的权值为k，源点与所有v1连接，汇点与所有男孩连接权值为mid（mid为0到n之间的数），然后，
二分枚举mid（0~n）跑最大流，找出是满流（即最大流为n*mid）的最大mid值，此mid值即为答案。
代码示例：
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<queue>#define Min(a,b) a<b?a:b#define inf 1000000000#define maxn 200000#define maxh 1000using namespace std;typedef struct //前向星 {    int to,next,w;}node;typedef struct{    int x,t;}dep;node E[maxn];int head[maxh],headx[maxh],deep[maxh],cnt;int map[maxh][maxh];int set[maxh];int s,t,k;/////////////////////////////////////////zuidaliu///////////////void init(){    memset(head,-1,sizeof(head));    cnt=0;}void add(int a,int b,int c){    E[cnt].to=b,E[cnt].w=c,E[cnt].next=head[a],head[a]=cnt++;    E[cnt].to=a,E[cnt].w=0,E[cnt].next=head[b],head[b]=cnt++;}int bfs(int s,int t,int n){    memset(deep,255,sizeof(deep));    dep fir,nex;    queue<dep>Q;    fir.x=s,fir.t=0,deep[s]=0;    Q.push(fir);    while(!Q.empty())    {        fir=Q.front();        Q.pop();        for(int i=head[fir.x];i+1;i=E[i].next)        {            nex.x=E[i].to;            nex.t=fir.t+1;            if(deep[nex.x]!=-1||!E[i].w)            continue;            deep[nex.x]=nex.t;            Q.push(nex);        }    }    for(int i=0;i<=n;i++)    headx[i]=head[i];    return deep[t]!=-1;}int dfs(int s,int t,int flow){    if(s==t)    return flow;    int newflow=0;    for(int i=headx[s];i+1;i=E[i].next)    {           headx[s]=i;        int to=E[i].to;        int w=E[i].w;        if(!w||deep[to]!=deep[s]+1)        continue;        int temp=dfs(to,t,min(w,flow-newflow));        newflow+=temp;        E[i].w-=temp;        E[i^1].w+=temp;        if(newflow==flow)        break;    }    if(!newflow)deep[s]=0;    return newflow;}int Dinic(int s,int t,int n){    int sum=0;    while(bfs(s,t,n))    {        sum+=dfs(s,t,inf);    }    return sum;}/////////////////////////////////bingcharji///////////////////////int findx(int x){    if(x!=set[x])    set[x]=findx(set[x]);    return set[x];}void fun(int x,int y){    x=findx(x);    y=findx(y);    if(x!=y)    set[x]=y;}/////////////////////////////////jiantu///////////////////////////void built(int mid,int n){       int n1=n,n2=2*n;    init(); //出始前向星     for(int i=1;i<=n;i++)    {        add(s,i,mid);        add(i+n2,t,mid);        add(i,i+n1,k);    }    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++)    {        if(map[i][j])        {            add(i,j+n2,1);        }        else        {            add(i+n1,j+n2,1);        }    }}////////////////////////////////zhuhanshu//////////////////////////////int main(){    int T,n,m,f;    int a,b,xi,yi;    int l,r,mid;    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d%d",&n,&m,&k,&f);        for(int i=0;i<=n;i++)        {            set[i]=i;            for(int j=0;j<=n;j++) //初始化             {                map[i][j]=0;            }        }        for(int i=0;i<m;i++)        {            scanf("%d%d",&a,&b);            map[a][b]=1;        }        for(int i=0;i<f;i++)        {            scanf("%d%d",&a,&b);            fun(a,b);        }        for(int i=1;i<=n;i++)        {            xi=findx(i);            for(int j=1;j<=n;j++)            {                yi=findx(j);                if(xi==yi&&i!=j)                {                    for(int l=1;l<=n;l++)                    {                        if(map[j][l])                        {                            map[i][l]=1;                        }                    }                }            }        }        l=0,r=n+1;        s=3*n+1,t=3*n+2;        while(l!=r-1)        {            mid=(l+r)/2;            built(mid,n);            int sum=Dinic(s,t,t);            if(sum==n*mid)            {                l=mid;            }            else            {                r=mid;            }        //    printf("sum=%d\n",sum);        }        printf("%d\n",l);    }    return 0;}