题目传送门：洛谷P5089。
题意简述：
一张 \(n \times m\) 的表格，有一些格子有标记，另外一些格子没有标记。
如果 \((r_1,c_1),(r_1,c_2),(r_2,c_1)\) （满足 \(r_1\ne r_2,c_1\ne c_2\)）都有标记，那么可以不花费任何代价使得 \((r_2,c_2)\) 也有标记。
你也可以花费 \(1\) 的代价使得任意一个格子有标记。
问使得所有格子都有标记的最小花费
题解：
比赛时这题我想了很久，猜了一个奇怪的结论交上去就对了。
这里贴一下官方题解的证明方法：
建立一张二分图，左边的点代表 \(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\)。
思路很巧妙，代码并不难写：
1 #include<bits/stdc++.h> 2 int n,m,q,x,y,S; 3 int v[400001]; 4 int h[400001],nxt[400001],to[400001],tot; 5 inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;} 6 void D(int u){ 7 for(int i=h[u];i;i=nxt[i])if(!v[to[i]]) 8 v[to[i]]=1, D(to[i]); 9 } 10 int main(){ 11 scanf("%d%d%d",&n,&m,&q); 12 while(q--) scanf("%d%d",&x,&y), ins(x,n+y), ins(n+y,x); 13 for(int i=1;i<=n+m;++i) if(!v[i]) ++S, v[i]=1, D(i); 14 printf("%d",S-1); 15 return 0; 16 }