自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 22:07:01，当前版本为作者最后更新于2018-12-10 21:08:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题也就是 Codeforces #500 的 Div1 B 题，所以说是双倍经验啦！

比赛时这题我想了很久，猜了一个奇怪的结论交上去就对了。

这里贴一下官方题解的证明方法：

建立一张二分图，左边的点代表 $n$ 个周期，右边的点代表 $m$ 个主族。

把每一个元素 $(x,y)$ 看作一条边，连接第 $x$ 周期和第 $y$ 主族。

那么我们的目标是是这个二分图变成完全二分图，也就是有 $n \times m$ 条边。

考虑核聚变的条件：
$(r_1, c_1) + (r_1, c_2) + (r_2, c_1) \to (r_2, c_2)$。

可以发现这个过程是不改变二分图中的连通分量的个数的。

而反过来，对于二分图中的某一个连通分量，也可以通过核聚变的方式，把这个连通分量变成“完全”的，也就是连接左右两部分的所有边都存在。

那么答案就是将这个二分图添加尽量少的边使得它联通的边数。

也就是：$\text{连通分量的个数}-1$。

思路很巧妙，代码并不难写：

#include<bits/stdc++.h>
int n,m,q,x,y,S;
int v[400001];
int h[400001],nxt[400001],to[400001],tot;
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}
void D(int u){
	for(int i=h[u];i;i=nxt[i])if(!v[to[i]])
		v[to[i]]=1, D(to[i]);
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	while(q--) scanf("%d%d",&x,&y), ins(x,n+y), ins(n+y,x);
	for(int i=1;i<=n+m;++i) if(!v[i]) ++S, v[i]=1, D(i);
	printf("%d",S-1);
	return 0;
}