题解 P5089 【[eJOI2018]元素周期表】

题解 P5089 【[eJOI2018]元素周期表】

题目链接

Solution [eJOI2018]元素周期表

题目大意:如果一个矩形有三个角被标记,另外一个角也会被标记.求最小要手动标记多少个点才能让已经有一些标记的矩阵全被标记

分析:这题思路真的神仙

可以用一个常用套路,整个(n)行(m)列的矩阵看做一个二分图,显然我们的目标图就是一个完全二分图

再来看核聚变的式子,我们发现聚变后新添加的边任然在原来的联通分量里面,也就是说它不会改变联通分量的个数

问题就是:一个有了一些边的二分图,问最少添加多少条边可以让它变成完全二分图

显然答案等于连通分量个数(-1),可以用并查集维护

#include <cstdio>
#include <cctype>
using namespace std;
const int maxn = 5e5 + 100;
inline int read(){int x = 0;char c = getchar();while(!isdigit(c))c = getchar();while(isdigit(c))x = x * 10 + c - '0',c = getchar();return x;
}
struct union_set{int f[maxn],siz;inline void init(int n){siz = n;for(int i = 1;i <= n;i++)f[i] = i;}inline int find(int x){return (x == f[x]) ? x : (f[x] = find(f[x]));}inline void merge(int a,int b){int x = find(a),y = find(b);if(x != y){siz--;f[x] = y;}}
}s;
int n,m,q;
int main(){n = read(),m = read(),q = read();s.init(n + m);for(int x,y,i = 1;i <= q;i++)x = read(),y = read() + (x,y);printf("%dn",s.siz - 1);return 0;
}

转载于:.html