首页 > 代码库 > HDU 3081：Marriage Match II（二分图匹配+并查集）
HDU 3081：Marriage Match II（二分图匹配+并查集）
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，直到不能完美匹配就退出。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 255 6 int vis[N], mp[N][N], fa[N], match[N], n; 7 int Find(int x) { if(x == fa[x]) return x; return fa[x] = Find(fa[x]); } 8 void Merge(int x, int y) { x = Find(x), y = Find(y); if(x != y) fa[x] = y; } 9 bool DFS(int u) {10 for(int i = 1; i <= n; i++) {11 if(mp[u][i] && !vis[i]) {12 vis[i] = 1;13 if(match[i] == -1 || DFS(match[i])) {14 match[i] = u;15 return true;16 }17 }18 }19 return false;20 }21 void solve() {22 int ans = 0, res;23 while(true) {24 res = 0;25 memset(match, -1, sizeof(match));26 for(int i = 1; i <= n; i++) {27 memset(vis, 0, sizeof(vis));28 if(DFS(i)) res++;29 }30 if(res != n) break;31 for(int i = 1; i <= n; i++) mp[match[i]][i] = 0;32 ans++;33 }34 printf("%d\n", ans);35 }36 int main() {37 int t;38 scanf("%d", &t);39 while(t--) {40 int m, k;41 scanf("%d%d%d", &n, &m, &k);42 for(int i = 1; i <= n; i++) fa[i] = i;43 memset(mp, 0, sizeof(mp));44 for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); mp[u][v] = 1; }45 for(int i = 1; i <= k; i++) { int u, v; scanf("%d%d", &u, &v); Merge(u, v); }46 for(int i = 1; i <= n; i++) // 传递47 for(int j = 1; j <= n; j++)48 if(Find(i) == Find(j))49 for(int x = 1; x <= n; x++) {50 if(mp[i][x]) mp[j][x] = 1;51 if(mp[j][x]) mp[i][x] = 1;52 }53 solve();54 }55 return 0;56 }
HDU 3081：Marriage Match II（二分图匹配+并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。