HDU 3081 Marriage Match II (网络流,最大流,二分,并查集)
Description
Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the game of playing house we used to play when we are kids. What a happy time as so many friends playing together. And it is normal that a fight or a quarrel breaks out, but we will still play together after that, because we are kids.
Now, there are 2n kids, n boys numbered from 1 to n, and n girls numbered from 1 to n. you know, ladies first. So, every girl can choose a boy first, with whom she has not quarreled, to make up a family. Besides, the girl X can also choose boy Z to be her boyfriend when her friend, girl Y has not quarreled with him. Furthermore, the friendship is mutual, which means a and c are friends provided that a and b are friends and b and c are friend.
Once every girl finds their boyfriends they will start a new round of this game—marriage match. At the end of each round, every girl will start to find a new boyfriend, who she has not chosen before. So the game goes on and on.
Now, here is the question for you, how many rounds can these 2n kids totally play this game?
Input
There are several test cases. First is a integer T, means the number of test cases.
Each test case starts with three integer n, m and f in a line (3<=n<=100,0<m<nn,0<=f<n). n means there are 2n children, n girls(number from 1 to n) and n boys(number from 1 to n).
Then m lines follow. Each line contains two numbers a and b, means girl a and boy b had never quarreled with each other.
Then f lines follow. Each line contains two numbers c and d, means girl c and girl d are good friends.
Output
For each case, output a number in one line. The maximal number of Marriage Match the children can play.
Sample Input
1
4 5 2
1 1
2 3
3 2
4 2
4 4
1 4
2 3
Sample Output
2
Http
HDU:https://cn.vjudge.net/problem/HDU-3081
Source
网络流,最大流,并查集,二分
题目大意
有2*n个点，现在前n个点与后n个点有若干对应关系，求有多少种二分图完美匹配的方案
解决思路
首先对于每一个对应关系,我们连容量为1的边.然后如何判断总共可以进行多少轮呢?因为我们还要将女孩与源点相连,将男孩与汇点相连.那么这个与汇点源点相连的边的容量就可以限制进行多少轮.假设我们已经知道可以进行x轮,那么如果我们将与汇点源点相连的边的容量都设为x,我们可以发现最大流就是n*x.有了这个结论,我们就可以二分这个x.每一次二分x,将连汇点源点的边容量设为x,然后跑最大流,如果满流(即流量==x*n)说明这个x是可行的,上调下边界,否则下调上边界.
至于如何判断朋友关系呢?可以通过并查集来实现.因为朋友关系是可传递的,所以一个集中只要有一个可以连,其他的都可以连.这又带来一个问题,就是判重,因为不能连重边,所以这里用Map[i][j]来判重,Map[i][j]为1时表示女孩i与男孩j有边相连.
另:这里用Dinic实现最大流,可以参考这篇文章
本题还可以用二分图匹配的方式完成,请参考这篇文章
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxN=301;
const int maxM=101*101*20;
const int inf=2147483647;
class Edge
{
public:
int u,v,flow;
};
int n,m;
int cnt=-1;
int Head[maxN];
int Head_[maxN];//这两个加了下划线的数组是用来将没有连上源点汇点的图存下来的,因为二分答案要多次进行最大流,只有练连了源点或汇点的边的容量会变,而这些边是不会变的,所以为了节约时间,不再重复建图
int Next[maxM];
Edge E[maxM];
Edge E2[maxM];
int cur[maxN];
int depth[maxN];
int Mayuri[maxN];
int Map[maxN][maxN];//判重
int Q[maxN];
void Add_Edge(int u,int v,int flow);
int max_flow(int value);
bool bfs();
int dfs(int u,int flow);
int Find(int u);
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
cnt=-1;//初始化
memset(Head,-1,sizeof(Head));
memset(Map,0,sizeof(Map));
int f;
scanf("%d%d%d",&n,&m,&f);
for (int i=1;i<=n;i++)//并查集初始化
Mayuri[i]=i;
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
Add_Edge(u,v+n,1);
Map[u][v]=1;
}
for (int i=1;i<=f;i++)
{
int u,v;
scanf("%d%d",&u,&v);
int fu=Find(u);
int fv=Find(v);
if (fu!=fv)
Mayuri[fu]=fv;
}
for (int i=1;i<=n;i++)//对于每一个朋友关系,连上对应的能连的边
for (int j=1;j<=n;j++)
if (Find(i)==Find(j))
for (int k=1;k<=n;k++)
if ((Map[i][k]==1)&&(Map[j][k]==0))
{
Map[j][k]=1;
Add_Edge(j,k+n,1);
}
int l=0,r=n*n;
int Ans;
while (l<=r)//二分答案
{
//cout<<l<<" "<<r<<endl;
int mid=(l+r)/2;
if (mid*n==max_flow(mid))
{
l=mid+1;
Ans=mid;
}
else
r=mid-1;
}
printf("%d\n",Ans);
}
}
void Add_Edge(int u,int v,int flow)
{
cnt++;
Next[cnt]=Head[u];
Head[u]=cnt;
E[cnt].u=u;
E[cnt].v=v;
E[cnt].flow=flow;
cnt++;
Next[cnt]=Head[v];
Head[v]=cnt;
E[cnt].u=v;
E[cnt].v=u;
E[cnt].flow=0;
}
int max_flow(int value)//求解最大流,value是当前二分的最大次数
{
int cnt_=cnt;//将图先备份一遍
for (int i=0;i<=2*n+1;i++)
Head_[i]=Head[i];
for (int i=0;i<=cnt;i++)
E2[i]=E[i];
for (int i=1;i<=n;i++)
{
Add_Edge(0,i,value);
Add_Edge(i+n,n*2+1,value);
}
int Ans=0;//求解最大流
while (bfs())
{
for (int i=0;i<=2*n+1;i++)
cur[i]=Head[i];
while (int di=dfs(0,inf))
Ans+=di;
}
cnt=cnt_;//把图换回来
for (int i=0;i<=2*n+1;i++)
Head[i]=Head_[i];
for (int i=0;i<=cnt;i++)
E[i]=E2[i];
//cout<<Ans<<endl;
return Ans;
}
bool bfs()
{
memset(depth,-1,sizeof(depth));
int h=1,t=0;
Q[1]=0;
depth[0]=1;
do
{
t++;
int u=Q[t];
for (int i=Head[u];i!=-1;i=Next[i])
{
int v=E[i].v;
if ((depth[v]==-1)&&(E[i].flow>0))
{
depth[v]=depth[u]+1;
h++;
Q[h]=v;
}
}
}
while (h!=t);
if (depth[n*2+1]==-1)
return 0;
return 1;
}
int dfs(int u,int flow)
{
if (u==n*2+1)
return flow;
for (int &i=cur[u];i!=-1;i=Next[i])
{
int v=E[i].v;
if ((depth[v]==depth[u]+1)&&(E[i].flow>0))
{
int di=dfs(v,min(flow,E[i].flow));
if (di>0)
{
E[i].flow-=di;
E[i^1].flow+=di;
return di;
}
}
}
return 0;
}
int Find(int u)
{
if (Mayuri[u]!=u)
Mayuri[u]=Find(Mayuri[u]);
return Mayuri[u];
}