【Solution】Muddy Fields G-二分图匹配

Posted on | In ,

题目传送门。

建模

二分图匹配的模型有两个要素：

  1. 节点能分成独立的两个集合，每个集合内部有 $0$ 条边：**$0$ 要素**

  2. 每个节点只能与 $1$ 条匹配边相连：**$1$ 要素**

    ——摘自李煜东《算法竞赛进阶指南》

分析一下这道题的两个要素：

  1. 每条横向木板之间互不交叉，每条纵向木板之间互不交叉：**$0$ 要素**
  2. 每个泥地仅能被 $1$ 条最优横向木板和 $1$ 条最优纵向木板包含：**$1$ 要素**

那我们可以以每个泥地为边，以包含其的最优横向木板和最优纵向木板为其左右端点，建立二分图。

题目要求最少木板数覆盖全部的泥地，这可以转化成一次操作可以选择一个点，将所连的边染色，目的是让所有边被染色，然后求最少需要的点数，即为二分图最小点覆盖。

而最小点覆盖等于最大匹配，二分图最大匹配的König定理及其证明 | Matrix67: The Aha Moments，故建图跑匈牙利即可。

匈牙利算法

每次找到一条未匹配-匹配-未匹配-$\cdots$-未匹配的路径，将其取反，得到总匹配数 $+1$。

这条路径被称为增广路。

好了相信你（我）已经学会匈牙利算法了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

const int N = 55;

bool map[N][N], g[N * N][N * N], vis[N * N];
int r[N][N], c[N][N], match[N * N];

int crow, ccol;

bool dfs(int x) {
	for (int y = 1; y <= ccol; ++y)
		if (g[x][y] && !vis[y]) {
			vis[y] = true;
			if (!match[y] || dfs(match[y])) return match[y] = x, true;
		}
	return false;
}

int main() {
#ifdef ONLINE_JUDGE
#endif
#ifdef LOCAL
	clock_t c1 = clock();
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif
	int n, m;
	char cc;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			std::cin >> cc;
			if (cc == '*') {
				map[i][j] = true;
				if (j == 1 || !map[i][j - 1]) ++crow;
				r[i][j] = crow;
			}
		}
	for (int j = 1; j <= m; ++j) {
		for (int i = 1; i <= n; ++i)
			if (map[i][j]) {
				if (i == 1 || !map[i - 1][j]) ++ccol;
				c[i][j] = ccol;
				g[r[i][j]][c[i][j]] = true;
			}
	}
	int ans = 0;
	for (int i = 1; i <= crow; ++i) {
		memset(vis, 0, sizeof vis);
		ans += int(dfs(i));
	}
	printf("%d", ans);
#ifdef LOCAL
	// 当运行暴力对拍时，请注释掉下面这行
	printf("\nTime used: %ldms.\n", clock() - c1);
#endif
	return 0;
}