首页 > 代码库 > HDU 3081 Marriage Match II【并查集+二分图最大匹配】
HDU 3081 Marriage Match II【并查集+二分图最大匹配】
大意：有n个男孩n个女孩，告诉你每个女孩喜欢哪些男孩，又告诉你女孩之间的存在一些朋友关系
一个女孩可以和她喜欢的男孩结婚也可以和她朋友喜欢的男孩结婚， 并且朋友关系可以传递
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?
问最后能进行多少轮game
分析：
用并查集处理处朋友的关系集合 把每个人到喜欢的男孩和其朋友喜欢的男孩建边
当最大匹配 == n 的时候 rounds++ 然后删除匹配边
求出round数即可
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 105; 8 const int INF = 1000000000; 9 10 int fa[maxn]; 11 void init(int x) { 12 for(int i = 0; i <= x; i++) { 13 fa[i] = i; 14 } 15 } 16 17 int find(int u) { 18 if(fa[u] == u) return u; 19 return fa[u] = find(fa[u]); 20 } 21 22 void unin(int u, int v) { 23 int fu = find(u); 24 int fv = find(v); 25 if(fu != fv) { 26 fa[fu] = fv; 27 } 28 } 29 30 31 int Link[maxn]; 32 int W[maxn][maxn]; 33 int vis[maxn]; 34 int n; 35 36 int Find(int i) { 37 for(int j = 1; j <= n; j++) { 38 if(W[i][j] && !vis[j]) { 39 vis[j] = 1; 40 if(Link[j] == -1 || Find(Link[j]) ) { 41 Link[j] = i; 42 return true; 43 } 44 } 45 } 46 return false; 47 } 48 49 bool Match() { 50 memset(Link, -1, sizeof(Link)); 51 for(int i = 1; i <= n; i++) { 52 memset(vis, 0, sizeof(vis)); 53 if(!Find(i)) return false; 54 } 55 return true; 56 } 57 58 int Solve() { 59 int cnt = 0; 60 while(1) { 61 if(Match() ) { 62 cnt ++; 63 for(int j = 1; j <= n; j++) { 64 W[Link[j]][j] = 0; 65 } 66 } else break; 67 } 68 return cnt; 69 } 70 71 vector<int> v[maxn * maxn]; 72 73 int main() { 74 int m, f; 75 int a, b; 76 int c, d; 77 int t; 78 scanf("%d", &t); 79 while(t--) { 80 scanf("%d %d %d", &n, &m, &f); 81 memset(W, 0, sizeof(W)); 82 init(n); 83 for(int i = 0; i <= n; i++) v[i].clear(); 84 for(int i = 1; i <= m; i++) { 85 scanf("%d %d", &a, &b); 86 v[a].push_back(b); 87 } 88 for(int i = 1; i <= f; i++) { 89 scanf("%d %d",&c, &d); 90 unin(c, d); 91 } 92 for(int i = 1; i <= n; i++) { 93 for(int j = 1; j <= n; j++) { 94 if(find(i) == find(j) ) { 95 for(int k = 0; k < v[j].size(); k++) { 96 W[i][v[j][k]] = 1; 97 } 98 } 99 }100 }101 printf("%d\n", Solve() ) ;102 }103 return 0;104 }
HDU 3081 Marriage Match II【并查集+二分图最大匹配】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。