0%

「AtCoder Japanese Student Championship 2019 Qualification E」Card Collector

好久没更了,水平下降严重 = =

AtCoder Japanese Student Championship 2019 Qualification E

题意

有 $n$ 个写着数字的卡片放在 $h\times w$ 的网格上,第一次你可以在每一行选择至多一张卡片取走,第二次在每一列选择至多一张卡片取走,要求最大化取走卡片上的数字总和。

同一个位置可能有多个卡片。

$n,h,w\le 10^5$

做法

个人做法可能不是很简洁

假设选择了若干卡片,判断能否分配每张卡片是在第几次取走。

我们可以构出一张二分图,左边是选择的卡片,右边是行和列,卡片向对应的行和列连边,因此左侧每个点的度都为 $2$,卡片集合是可行的当且仅当最大匹配大小是卡片数。

右侧有一些度数为 $1$ 的点,我们可以不断把这些点干掉,直到右边所有点的度数至少为 $2$。

可以发现一个条件是右侧点数不少于左侧点数,而在干掉无用的点之后右侧点数不多于左侧点数,点数相等当且仅当所有点度数为 $2$。

因此整个图是若干个环,加上之前忽略的点之后是环套树森林,即卡片集合合法当且仅当按照上述方法构出的图是环套树森林。

类似 Kruskal 地用并查集维护每个联通块即可。

事实上最后不需要左侧代表卡片的点,每个点可以变成一条边。

复杂度 $\mathcal O(n \log n)$

代码

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
#include<bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 100005, M = 200005;
ll ans;
int n, h, w, f[M];
bool g[M];
struct wish{
int r, c, a;
bool operator<(const wish &r)const{ return a>r.a;}
} a[N];
int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}
bool combine(int x, int y){
x=find(x), y=find(y);
if(x==y) if(g[x]) return 0; else return g[x]=1, 1;
else if(g[x]+g[y]>1) return 0; else return f[x]=y, g[y]|=g[x], 1;
}
int main() {
scanf("%d%d%d", &n, &h, &w);
for(int i=1; i<=n; ++i) scanf("%d%d%d", &a[i].r, &a[i].c, &a[i].a);
sort(a+1, a+n+1);
for(int i=1; i<=h+w; ++i) f[i]=i;
for(int i=1; i<=n; ++i) if(combine(a[i].r, h+a[i].c)) ans+=a[i].a;
printf("%lld\n", ans);
return 0;
}