「AtCoder」「JSC 2019 Qual E」Card Collector
题目传送门
题意
一个 \(H\times W\) 的矩阵，有 \(n\) 个位置有卡片，每张卡片上有个数字 \(a_i\)。你可以在每行拿走一张卡片，然后在每列拿走一张卡片，求拿走的卡片的 \(a_i\) 之和的最大值。
\(1\le H,W,n,a_i\le 10^5\)
题解
假设有 \(H+W\) 个点，第 \(1\sim H\) 个点表示行，第 \(H+1\sim H+W\) 个点表示列。第 \(i\) 行第 \(j\) 列的卡片对应一条 \(i\) 到 \(H+j\) 的边，边权为卡片上的数字。我们把所有拿走的卡片对应的边拿出来，显然会形成一个环套树森林。简单证明一下：
假设边是有向的，在第 \(i\) 行选了第 \(j\) 列的卡片，则选择 \(i\) 到 \(H+j\) 的有向边；在第 \(i\) 列选了第 \(j\) 行的卡片，则选择 \(H+i\) 到 \(j\) 的有向边。那么每个点有且仅有一条出边，所以这是一个环套内向树森林。忽略边的方向，则是环套树森林。
相当于我们要求出一个原图的边权之和最大的“生成环套树森林”。用类似于求最大生成树的 Kruskal 算法贪心选边即可。
代码
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
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
int read(){
register int x = 0;
register char f = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f ^= 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
int n, h, w, fa[200005], g[200005];
long long ans;
struct node{
int r, c, v;
bool operator < (const node &rhs) const {
return v > rhs.v;
}
}a[100005];
int find(int x){
return fa[x] == x ? x : (fa[x] = find(fa[x]));
}
bool merge(int x, int y){
x = find(x), y = find(y);
if (x == y) if (g[x]) return 0; else return g[x] = 1, 1;
if (g[x] && g[y]) return 0;
return fa[y] = x, g[x] |= g[y], 1;
}
int main(){
n = read(), h = read(), w = read();
for (register int i = 1; i <= n; ++i)
a[i].r = read(), a[i].c = read(), a[i].v = read();
std :: sort(a + 1, a + 1 + n);
for (register int i = 1; i <= h + w; ++i) fa[i] = i, g[i] = 0;
for (register int i = 1; i <= n; ++i)
if (merge(a[i].r, a[i].c + h)) ans += a[i].v;
printf("%lld\n", ans);
}
|
