Marriage Match II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1095 Accepted Submission(s): 393
Problem 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?
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.
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
Author
starvae
Source
Recommend
lcy
女生和男生配对,有些女生相互是朋友,每个女生也可以跟她朋友所配对的男生配对
每次配对,每个女生都要跟不同的男生配对。问最多能配对几轮。
最大流,用并查集处理女生之间的朋友关系,最少配0轮,最多配n轮,二分解之,源点向女生建边,男生向汇点建边,容量均为mid,女生跟所有能配对的男生连线,容量为1,如果最大流 = mid * n,那mid就就能做到mid轮配对
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=1010; const int EM=500010; const int INF=0x3f3f3f3f; int n,m,f,cnt,head[VM]; int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM]; int father[VM],vis[VM][VM]; struct Edge{ int u,v,nxt; int cap; }edge[EM]; struct node{ int x,y; }child[EM]; void makeSet(){ for(int i=1;i<=n;i++){ father[i]=i; } } int findSet(int x){ if(x!=father[x]){ father[x]=findSet(father[x]); } return father[x]; } void Union(int x,int y){ int fx=findSet(x); int fy=findSet(y); if(fx!=fy) father[fx]=fy; } void addedge(int cu,int cv,int cw){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].u=cv; edge[cnt].v=cu; edge[cnt].cap=0; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; int SAP(int n){ int max_flow=0,u=src,v; int id,mindep; aug[src]=INF; pre[src]=-1; memset(dep,0,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=n; for(int i=0;i<=n;i++) cur[i]=head[i]; // 初始化当前弧为第一条弧 while(dep[src]<n){ int flag=0; if(u==des){ max_flow+=aug[des]; for(v=pre[des];v!=-1;v=pre[v]){ // 路径回溯更新残留网络 id=cur[v]; edge[id].cap-=aug[des]; edge[id^1].cap+=aug[des]; aug[v]-=aug[des]; // 修改可增广量,以后会用到 if(edge[id].cap==0) // 不回退到源点,仅回退到容量为0的弧的弧尾 u=v; } } for(int i=cur[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; // 从当前弧开始查找允许弧 if(edge[i].cap>0 && dep[u]==dep[v]+1){ // 找到允许弧 flag=1; pre[v]=u; cur[u]=i; aug[v]=min(aug[u],edge[i].cap); u=v; break; } } if(!flag){ if(--gap[dep[u]]==0) /* gap优化,层次树出现断层则结束算法 */ break; mindep=n; cur[u]=head[u]; for(int i=head[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; if(edge[i].cap>0 && dep[v]<mindep){ mindep=dep[v]; cur[u]=i; // 修改标号的同时修改当前弧 } } dep[u]=mindep+1; gap[dep[u]]++; if(u!=src) // 回溯继续寻找允许弧 u=pre[u]; } } return max_flow; } void build(int mid){ src=0,des=2*n+1; cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++){ addedge(src,i,mid); addedge(i+n,des,mid); } memset(vis,0,sizeof(vis)); for(int i=0;i<m;i++){ int a=child[i].x; int b=child[i].y; for(int j=1;j<=n;j++) if(father[a]==father[j] && !vis[j][b]){ vis[j][b]=1; addedge(j,n+b,1); } } } int main(){ //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&f); for(int i=0;i<m;i++) scanf("%d%d",&child[i].x,&child[i].y); makeSet(); int a,b; while(f--){ scanf("%d%d",&a,&b); Union(a,b); } for(int i=1;i<=n;i++) father[i]=findSet(i); int low=0,high=n,ans=0,mid; while(low<=high){ mid=(low+high)>>1; build(mid); if(SAP(2*n+2)==n*mid){ low=mid+1; ans=mid; }else high=mid-1; } printf("%d\n",ans); } return 0; }
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
HDUACM2010版13二分匹配及其应用.ppt
应同学之邀帮忙发布的一篇勘误 【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队...直接定义二维状态有很多浪费的空间,可以考虑u
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
hdu acm 教案 二分匹配及其应用 hdu acm 教案 二分匹配及其应用
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU图论题目分类
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu题目分类
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划...(lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码