题解 AT5168 【Card Collector】
Lice
2020-08-04 19:35:21
### Description
现有 $h$ 行 $w$ 列的网格。给定 $n$ 张卡片，每张卡片 $i$ 有一个位置 $(r_i, c_i)$ 以及数字 $a_i$。
你可以先在每一行拿走不超过一个卡片，然后在每一列再拿不超过一个。不能重复拿。
求最后可得的卡片上数字之和的最大值。
### Hint
- $1\le n, w, h\le 10^5$
- $a_i \in [1, 10^5]$
- $1\le r_i \le h, 1\le c_i \le w$
### Solution
*Reference : https://autumnkite.github.io/atcoder-jsc19qualE-sol/*
如果把每一行、列都视作一个点，把卡片视为边，我们会得到一个 $w+h$ 个点， $n$ 条边的图。若有一张第 $i$ 行第 $j$ 列的卡片，那么就视作一条结点 $i$，$h+j$ 之间的边，权值为卡片数值。
考虑题面上取卡片的过程如何转换到图上：我们假定图有向，那么在第 $i$ 行取走第 $j$ 列的卡片，就相当于一条 $i\to j+h$ 的边；同理，在第 $i$ 列取走第 $j$ 行的卡片，就相当于一条 $i + h\to j$ 的边。
试着研究最后取完建出的新图的性质。一个结点的出度最多为 $1$，那么整个新图就是（内向）基环树的森林。最后将边转为无向。
题目要求权值最大化，那么就是求图上的最大生成基环树森林。要求最大生成基环树森林，可以仿照 Kruskal 算法贪心地取边，与一般 MST 的不同之处就是需要判环，实现要点是一个点所在连通块中最多一个环。
时间复杂度 $O(n\log n)$。
### Code
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, w, h;
struct edge { int u, v, w; } e[N];
int fa[N << 1];
bool ring[N << 1];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> h >> w;
for (int i = 1; i <= w + h; i++)
fa[i] = i, ring[i] = false;
for (int i = 1; i <= n; i++)
cin >> e[i].u >> e[i].v >> e[i].w;
sort(e + 1, e + 1 + n, [](const edge& x, const edge& y) {
return x.w > y.w;
});
long long ans = 0ll;
for (int i = 1; i <= n; i++) {
int u = e[i].u, v = e[i].v + h, w = e[i].w;
u = find(u), v = find(v);
if (u == v) {
if (!ring[u]) ring[u] = 1, ans += w;
} else {
if (!ring[u] || !ring[v]) {
ring[u] = ring[v] = ring[u] | ring[v];
fa[u] = v, ans += w;
}
}
}
printf("%lld\n", ans);
return 0;
}
```