題干：

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<n*n,0<=f<n). n means there are 2*n 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

題目大意：

n個女生與n個男生配對，每個女生只能配對某些男生，有些女生相互是朋友，每個女生也可以跟她朋友能配對的男生配對。

每次配對，每個女生都要跟不同的男生配對且每個女生都能配到對。問最多能配對幾輪。

解題報告：（貼一個題解鏈接）

考慮用網絡流做，首先女生可以與她朋友能配對的男生配對，這樣需要用并查集保存他們可以配對的關系。

為了保證每一輪所有女生和男生都能匹配到，我們需要二分源點和女生、男生和匯點之間的容量k，并且需要保證滿流。找到最大的滿足條件的k就是答案。

解法的正確性可以用數學歸納法證明，當k=1時，轉化為一個二分匹配，如果滿流，就說明可以進行一輪。當k-1輪可以實現時（k-1滿流），如果容量為k時滿流，說明也可以實現k輪。這樣就證明了正確性。

由這個解法我們也可以想到用二分匹配的方法來解決：進行二分圖的最大匹配，在匹配完成后判斷匹配數是否等于n，不是的話說明GAME OVER 求得答案，是的話說明游戲能完成，然后進行刪邊操作，再繼續匹配，直到匹配數<n則得到答案。

AC代碼：

#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #include<set> using namespace std; const int INF = 0x3f3f3f3f; int tot; struct Edge {int to,ne,w; } e[1000005 * 2]; int head[10005]; int st,ed; int dis[10050],q[10005];//一共多少個點跑bfs，dis數組和q數組就開多大。 void add(int u,int v,int w) {e[++tot].to=v; e[tot].w=w; e[tot].ne=head[u]; head[u]=tot;e[++tot].to=u; e[tot].w=0; e[tot].ne=head[v]; head[v]=tot; } bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail) {int cur = q[front];if(cur == ed) return 1;front++;for(int i = head[cur]; i!=-1; i = e[i].ne) {if(e[i].w&&dis[e[i].to]<0) {q[tail++]=e[i].to;dis[e[i].to]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1; } int dfs(int cur,int limit) {//limit為源點到這個點的路徑上的最小邊權 if(limit==0||cur==ed) return limit;int w,flow=0;for(int i = head[cur]; i!=-1; i = e[i].ne) { if(e[i].w&&dis[e[i].to]==dis[cur]+1) {w=dfs(e[i].to,min(limit,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;limit-=w;if(limit==0) break;}}if(!flow) dis[cur]=-1;return flow; } int dinic() {int ans = 0;while(bfs(st,ed)) ans+=dfs(st,0x7fffffff);return ans; } int v[100005],u[100005],n,m,f; int fa[100005]; bool has[555][555]; int getf(int v) {return fa[v] == v ? v : fa[v] = getf(fa[v]); } bool ok(int x) {//每次都要重新建圖 tot=1;memset(head,-1,sizeof head);for(int i = 1; i<=n; i++) add(st,i,x);for(int i = 1; i<=n; i++) add(n+i,ed,x);//設為INF也可以？？答：并不可以 // for(int i = 1; i<=m; i++) add(u[i],n+v[i],1);for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) if(has[i][j]) add(i,j+n,1);}int ans = dinic();if(x*n == ans) return 1;else return 0; } int main() {int t;cin>>t;while(t--) {scanf("%d%d%d",&n,&m,&f);memset(has,0,sizeof has);for(int i = 1; i<=n; i++) fa[i]=i;st=2*n+1,ed=st+1;for(int i = 1; i<=m; i++) {//u女v男 scanf("%d%d",u+i,v+i);has[u[i]][v[i]]=1;}for(int u,v,i = 1; i<=f; i++) {//f對女生 scanf("%d%d",&u,&v);u=getf(u),v=getf(v);fa[u]=v;}for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(getf(i)==getf(j))for(int k=1;k<=n;++k)if(has[i][k])has[j][k]=1;int l = 0,r = n,mid,ans=0;while(l<=r) {mid=(l+r)>>1;if(ok(mid)) l=mid+1,ans=mid;else r = mid-1;}printf("%d\n",ans); }return 0; }

總結：

錯誤想法1：S-Girl和Boy-T設成INF，然后跑一次最大流，然后答案為S-Girl和Boy-T的邊中流量的最小值，為什么不行。

給一組樣例：

1 3 4 0 1 2 2 1 2 3 3 2

答案應該是0，但用上述方法答案為1。

錯誤想法2：

考慮到n個女生和n個男生不重復完全配對最多只能進行n輪，想到可以將源點和女生、男生和匯點之間的容量賦為n，求出最大流。但是發現這樣是不行的，如果有女生或者男生一直無法配對，則答案本應是0，但是最大流肯定是>0的，所以答案是不對的。這個想法錯就錯在沒有抓住那個關鍵點：每一次舞會一定是男生女生全員參與，也就是抽象成：女生這邊都流出1的流量總有所有的男生全部接受到，也就是男生這邊接收到的流量總是等量的，不能是：1號男生接受到2流量，2號男生沒有流量流過。

錯誤想法3：

為什么不能直接把男生和匯點的流量設置為INF？

答：這也是和錯誤想法2差不多相同的錯誤。你這樣沒法保證每個男生接受的流量總是等量的。

?

本來想著是把左側的點再拆成n個點，然后對應連到右邊，后來發現沒啥意義，可以直接連到右邊的。

不過本來還有個想法，那就是把她和她的朋友關系直接轉化到左邊的點（女生之間的點）相連，而不直接轉化到和男生的對應關系，但是后來發現這樣是不行的，因為你這樣沒法控制每一輪，每個女生只能和一個男生建立關系，因為你這樣相當于把她倆女生當成一個完全一致的物品去看待了，但是其實她倆肯定是有區別的。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【HDU - 3081】Marriage Match II（网络流最大流，二分+网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。