NC20483 假期的宿舍 || 二分图最大匹配
二分图：一侧是床，一侧是要住的人（本校不回家的和非本校的）。
读入是否为本校的和是否回家的用数组记录，图两侧仍都为N个点，只不过不满足要求的就无法连边（相当于男女生不互相喜欢）。最后检查ans是否等于本校不回家的和非本校的人数之和即可。
在单独处理自己可以睡自己床时，注意只有这个人是本校的且不回家的时候才连边，因为要是回家根本就不会睡在床上，空床可以留给别人睡。
还要注意多组数据，链式前向星全部重新初始化。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e4 + 7; const int N = 55; typedef long long ll; int head[maxn], vis[N], match[N], cnt, stu[N], home[N]; struct edge { int to, next; }e[maxn]; void add(int u, int v) { e[++cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } bool dfs(int x) { for(int i = head[x]; i; i = e[i].next) { int v = e[i].to; if(!vis[v]) { vis[v] = 1; if(!match[v] || dfs(match[v])) { match[v] = x; return 1; } } } return 0; } int main() { int t; cin >> t; while(t--) { int n, x, ans = 0, r = 0; scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &stu[i]); if(!stu[i]) ++r; } for(int i = 1; i <= n; ++i) { scanf("%d", &home[i]); if(stu[i] && !home[i]) ++r; } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { scanf("%d", &x); if(i == j && stu[i] && !home[i]) { add(i, i); continue; } if(x) { if((stu[i] && stu[j] && !home[j]) || (stu[i] && !stu[j])) add(i, j); if((stu[j] && stu[i] && !home[i]) || (stu[j] && !stu[i])) add(j, i); } } } for(int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(vis)); ans += dfs(i); } if(ans == r) printf("^_^ "); else printf("T_T "); memset(head, 0, sizeof(head)); memset(match, 0, sizeof(match)); cnt = 0; memset(stu, 0, sizeof(stu)); memset(home, 0, sizeof(home)); memset(e, 0, sizeof(e)); } }
NC51316 Going Home || 二分图最大权完美匹配
由于是求最小的总花费，那么我们取相反数，就转化成求最大权了。输出时也要取负。
板子里已经包含每次的初始化操作了，所以即使是多组数据也可直接使用。每次需要提供val[][]，n，m即可。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e4 + 7; const int N = 111; const int INF = 0x3f3f3f3f; typedef long long ll; int val[N][N], vis_a[N], vis_b[N], match[N]; int ex_a[N], ex_b[N], n, m; struct house { int x, y; }h[N], man[N]; bool dfs(int x) { vis_a[x] = 1; for(int i = 1; i <= m; ++i) { if(!vis_b[i] && ex_a[x] + ex_b[i] == val[x][i]) { vis_b[i] = 1; if(!match[i] || dfs(match[i])) { match[i] = x; return 1; } } } return 0; } ll km() { memset(match, 0, sizeof(match)); fill(ex_b + 1, ex_b + 1 + n, 0); for(int i = 1; i <= n; ++i) { ex_a[i] = val[i][1]; for(int j = 2; j <= m; ++j) ex_a[i] = max(ex_a[i], val[i][j]); } for(int i = 1; i <= m; ++i) { while(1) { memset(vis_a + 1, 0, sizeof(vis_a[0]) * n); memset(vis_b + 1, 0, sizeof(vis_b[0]) * m); if(dfs(i)) break; int d = INF; for(int j = 1; j <= n; ++j) if(vis_a[j]) for(int k = 1; k <= m; ++k) if(!vis_b[k]) d = min(d, ex_a[j] + ex_b[k] - val[j][k]); for(int j = 1; j <= n; ++j) if(vis_a[j]) ex_a[j] -= d; for(int j = 1; j <= m; ++j) if(vis_b[j]) ex_b[j] += d; } } ll ans = 0; for(int i = 1; i <= n; ++i) { if(match[i]) ans += val[match[i]][i]; } return ans; } int main() { int nn, mm; while(scanf("%d %d", &nn, &mm)) { char c; n = 0; int hcnt = 0, mcnt = 0; if(nn == 0 && mm == 0) break; for(int i = 1; i <= nn; ++i) for(int j = 1; j <= mm; ++j) { scanf(" %c", &c); if(c == 'H') { ++n; h[++hcnt].x = i; h[hcnt].y = j; } else if(c == 'm') { man[++mcnt].x = i; man[mcnt].y = j; } } m = n; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) val[i][j] = -INF; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { val[i][j] = 0; val[i][j] += abs(man[i].x - h[j].x); val[i][j] += abs(man[i].y - h[j].y); val[i][j] = -val[i][j]; } } cout << -km() << endl; } }
NC107638 Asteroids || 二分图最大匹配等于最小点覆盖
用最少的炸弹炸所有的陨石。
用最少的点覆盖所有的边。
而炸弹每次炸一行或一列。
所以点 <=> 行、列，边 <=> 陨石。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e4 + 7; const int N = 555; const int INF = 0x3f3f3f3f; typedef long long ll; int head[maxn], vis[N], match[N], cnt; struct edge { int to, next; }e[maxn]; void add(int u, int v) { e[++cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } bool dfs(int x) { for(int i = head[x]; i; i = e[i].next) { int v = e[i].to; if(!vis[v]) { vis[v] = 1; if(!match[v] || dfs(match[v])) { match[v] = x; return 1; } } } return 0; } int main() { int n, k, r, c, ans = 0; scanf("%d %d", &n, &k); for(int i = 1; i <= k; ++i) { scanf("%d %d", &r, &c); add(r, c); } for(int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(vis)); ans += dfs(i); } cout << ans << endl; }
NC20472 矩阵游戏 || 二分图最大匹配
通过交换行列的操作使得主对角线上的格子均为黑色。输出是否可行。
也就是要求，第i行的第i个格子是黑色。只要找到一组n个点，位于不同行不同列，那么就可以通过交换行列使得主对角线上的格子均为黑色。因为交换行列时它们互不影响。每个点向着它的目标移动即可。比如，位于(4, 1)的点要去(1, 1)或(4, 4)，那么交换第一行和第四行，或者交换第一列和第四列。要不全进行行操作，要不全进行列操作。（如果直接向结果努力的话，当然这只是众多可行操作中的一种）