「AtCoder」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)\)

代码

#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;
}