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
", Solve() ) ;
102     }
103     return 0;
104 }

View Code