本文主要是介绍HDU 3277Marriage Match III（二分+并查集+拆点+网络流之最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：HDU 3277
这题跟这题的上一版建图方法差不多，只不过需要拆点。这个点拆的也很巧妙，既限制了流量，还只限制了一部分，以前一直以为拆点会全部限制，原来也可以用来分开限制，学习了。
建图方法为：建一源点与汇点，将女孩进行拆点，拆成i和i+n，将i与源点连边，权值为mid，将i与i+n连边，权值为k，再将男孩与汇点连边，权值为mid，这时可以配对的就将i与相应的男孩连边，权值为1，不能配对的就将i+n与对应的男孩连边，这样的话对原来可配对的不会限制流量，对不可以配对的限制了流量k。最后判断是否满流。
这次居然又卡在了并查集上。。。。= = ！简直无语。。不过这次卡是卡在优化上，这次的数据量比较大，利用上次的方法会TLE，于是这次不能再采用上次的方法了，这次是先对每个父节点可配对的进行标记，然后直接一次遍历即可。上一次的是对每个集合内的分别进行配对标记。。对并查集的运用还是不灵活。。
代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int head[800], source, sink, nv, cnt;
int cur[800], d[800], num[800], pre[800], q[800], bin[800], _hash[300][300];
struct N
{int boy, girl;
}pari[1000000];
int find1(int x)
{return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void merger(int x, int y)
{int f1=find1(x);int f2=find1(y);if(f2!=f1)bin[f2]=f1;
}
struct node
{int u, v, cap, next;
}edge[1000000];
void add(int u, int v, int cap)
{edge[cnt].v=v;edge[cnt].cap=cap;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].v=u;edge[cnt].cap=0;edge[cnt].next=head[v];head[v]=cnt++;
}
void bfs()
{memset(d,-1,sizeof(d));memset(num,0,sizeof(num));queue<int>q;q.push(sink);d[sink]=0;num[0]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(d[v]==-1){d[v]=d[u]+1;num[d[v]]++;q.push(v);}}}
}
int isap()
{memcpy(cur,head,sizeof(cur));bfs();int flow=0, u=pre[source]=source, i;while(d[source]<nv){if(u==sink){int f=INF, pos;for(i=source;i!=sink;i=edge[cur[i]].v){if(f>edge[cur[i]].cap){f=edge[cur[i]].cap;pos=i;}}for(i=source;i!=sink;i=edge[cur[i]].v){edge[cur[i]].cap-=f;edge[cur[i]^1].cap+=f;}flow+=f;u=pos;}for(i=cur[u];i!=-1;i=edge[i].next){if(d[edge[i].v]+1==d[u]&&edge[i].cap){break;}}if(i!=-1){cur[u]=i;pre[edge[i].v]=u;u=edge[i].v;}else{if(--num[d[u]]==0) break;int mind=nv;for(i=head[u];i!=-1;i=edge[i].next){if(mind>d[edge[i].v]&&edge[i].cap){mind=d[edge[i].v];cur[u]=i;}}d[u]=mind+1;num[d[u]]++;u=pre[u];}}return flow;
}
int main()
{int t, n, m, k, f, i, j, a, b;scanf("%d",&t);while(t--){scanf("%d%d%d%d",&n,&m,&k,&f);for(i=1;i<=m;i++){scanf("%d%d",&pari[i].girl,&pari[i].boy);}for(i=1;i<=n;i++){bin[i]=i;}while(f--){scanf("%d%d",&a,&b);merger(a,b);}int high=n, low=0, mid, ans, x;while(low<=high){mid=(low+high)/2;source=0;sink=3*n+1;nv=sink+1;memset(head,-1,sizeof(head));cnt=0;memset(_hash,0,sizeof(_hash));for(i=1;i<=n;i++){add(source,i,mid);add(i,i+n,k);add(2*n+i,sink,mid);}for(i=1;i<=m;i++){int a=pari[i].girl;int b=pari[i].boy;_hash[find1(a)][b]=1;}for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(_hash[find1(i)][j]){add(i,j+2*n,1);}else{add(i+n,j+2*n,1);}}}x=isap();if(x>=n*mid){ans=mid;low=mid+1;}else{high=mid-1;}}printf("%d\n",ans);}return 0;
}
这篇关于HDU 3277Marriage Match III（二分+并查集+拆点+网络流之最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
