题解 P5089 【[eJOI2018]元素周期表】
小粉兔
·
·
题解
这题也就是 Codeforces #500 的 Div1 B 题，所以说是双倍经验啦！
比赛时这题我想了很久，猜了一个奇怪的结论交上去就对了。
这里贴一下官方题解的证明方法：
建立一张二分图，左边的点代表 n 个周期，右边的点代表 m 个主族。
把每一个元素 (x,y) 看作一条边，连接第 x 周期和第 y 主族。
那么我们的目标是是这个二分图变成完全二分图，也就是有 n \times m 条边。
考虑核聚变的条件：
可以发现这个过程是不改变二分图中的连通分量的个数的。
而反过来，对于二分图中的某一个连通分量，也可以通过核聚变的方式，把这个连通分量变成“完全”的，也就是连接左右两部分的所有边都存在。
那么答案就是将这个二分图添加尽量少的边使得它联通的边数。
也就是：$\text{连通分量的个数}-1$。
思路很巧妙，代码并不难写：
```cpp
#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;
}
```