HDU 3081：Marriage Match II（二分图匹配+并查集）

时间：2023-11-26 08:53:44

http://acm.hdu.edu.cn/showproblem.php?pid=3081

题意：有n个男生n个女生，他们只有没有争吵或者女生a与男生A没有争吵，且女生b与女生a是朋友，因此女生b也可以和男生A过家家（具有传递性）。给出m个关系，代表女生a和男生b没有争吵过。给出k个关系，代表女生a与女生b是好朋友。每一轮过家家之后，女生只能选择可以选择并且没选过的男生过家家，问游戏能进行几轮。

思路：因为n<=100，因此支持O（n^3）的算法，挺容易想到是一个二分图匹配的。（出现在我的网络流专题里。让我想了好久最大流的做法。做完后搜题解才发现有二分答案然后跑最大流的做法）。用邻接矩阵做比较方便，一开始用并查集处理女生的集合，然后暴力枚举，处理出传递性。然后每次跑完匈牙利算法，就把这次匹配的边去掉（保证不会重复），并且答案加1，直到不能完美匹配就退出。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define N 255

 int vis[N], mp[N][N], fa[N], match[N], n;

 int Find(int x) { if(x == fa[x]) return x; return fa[x] = Find(fa[x]); }

 void Merge(int x, int y) { x = Find(x), y = Find(y); if(x != y) fa[x] = y; }

 bool DFS(int u) {

     for(int i = ; i <= n; i++) {

         if(mp[u][i] && !vis[i]) {

             vis[i] = ;

             if(match[i] == - || DFS(match[i])) {

                 match[i] = u;

                 return true;

             }

         }

     }

     return false;

 }

 void solve() {

     int ans = , res;

     while(true) {

         res = ;

         memset(match, -, sizeof(match));

         for(int i = ; i <= n; i++) {

             memset(vis, , sizeof(vis));

             if(DFS(i)) res++;

         }

         if(res != n) break;

         for(int i = ; i <= n; i++) mp[match[i]][i] = ;

         ans++;

     }

     printf("%d\n", ans);

 }

 int main() {

     int t;

     scanf("%d", &t);

     while(t--) {

         int m, k;

         scanf("%d%d%d", &n, &m, &k);

         for(int i = ; i <= n; i++) fa[i] = i;

         memset(mp, , sizeof(mp));

         for(int i = ; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); mp[u][v] = ; }

         for(int i = ; i <= k; i++) { int u, v; scanf("%d%d", &u, &v); Merge(u, v); }

         for(int i = ; i <= n; i++) // 传递

             for(int j = ; j <= n; j++)

                 if(Find(i) == Find(j))

                     for(int x = ; x <= n; x++) {

                         if(mp[i][x]) mp[j][x] = ;

                         if(mp[j][x]) mp[i][x] = ;

                     }

         solve();

     }

     return ;

 }

相关文章