题目大意
在一个 $n \times m$ 个棋盘上，每一行要放置一个守卫，每一列要放置一个守卫，行和列的守卫不能重复。在第 $i$ 行，第 $j$ 列放置守卫的代价是 $A(i, j)$，问花费的最小代价。
数据范围：$n \times m \le 10^5, n, m \ge 2$。
思路分析
这显然是一个费用流的模型。由于数据范围比较大，我们只需要使用模拟费用流的技巧即可。不好意思读错剧本了。
考虑一个守卫，它要么是管理所在行的，要么是管理所在列的。每一行和每一列都唯一对应一个守卫。我们将行和列都看作点，选中的守卫看作一条有向边。如果该守卫管理行，那么边朝向行；否则它管理列，那么边朝向列。这样，我们发现每一个点的入度都是 $1$，所以这些边形成了一片基环内向树森林。于是这道题就变成了求一个图的最小生成基环树森林。
事实上，我们只需要使用改动后的 Kruskal 算法就可以解决这个问题。对于每一个联通块，我们允许它有一条非树边。对于每条边，如果它的两端在同一个联通块里并且该联通块目前是树，那么把这条边加上并把联通块设为基环树；如果它的两端不在同一个联通块里且两个点所在的两个联通块不全是基环树，那么也可以将其合并，得到的新联通块要么是树要么是基环树。可以证明上述算法是正确的。时间复杂度 $O(nm \log nm)$。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | typedef long long ll; |
6 | const int maxn = 1e5; |
7 | int n, m, tot, cnt, fa[maxn + 3]; |
8 | bool b[maxn + 3]; |
9 | |
10 | struct edge { |
11 | int u, v, w; |
12 | friend bool operator < (const edge &a, const edge &b) { |
13 | return a.w < b.w; |
14 | } |
15 | } e[maxn + 3]; |
16 | |
17 | int find(int x) { |
18 | return fa[x] == x ? x : fa[x] = find(fa[x]); |
19 | } |
20 | |
21 | int main() { |
22 | scanf("%d %d", &n, &m); |
23 | for (int i = 1; i <= n; i++) { |
24 | for (int j = 1; j <= m; j++) { |
25 | scanf("%d", &e[++cnt].w); |
26 | e[cnt].u = i, e[cnt].v = n + j; |
27 | } |
28 | } |
29 | for (int i = 1; i <= n + m; i++) { |
30 | fa[i] = i, b[i] = false; |
31 | } |
32 | sort(e + 1, e + cnt + 1); |
33 | ll ans = 0; |
34 | for (int i = 1; i <= cnt; i++) { |
35 | int u = find(e[i].u), v = find(e[i].v); |
36 | if (b[u] + b[v] + (u == v) > 1) continue; |
37 | if (u != v) fa[u] = v, b[v] |= b[u], b[u] = false; |
38 | else b[u] = true; |
39 | ans += e[i].w; |
40 | } |
41 | printf("%lld\n", ans); |
42 | return 0; |
43 | } |