永乐国际在线永乐国际在线


F66永乐集团在线

Codeforces Round #500 (Div. 2) D - Chemical table

首先我们如果满足三缺一,那么必有同行和同列的点

如果两行有同列的数,我们可以设想,他们最后会全部填充成为两者啥都有的情况显然这个是个并查集现在我们有了很多集合,每个集合自己可以进行三缺一操作,但是集合有缺陷,集合里面的人都没有的列数,那就没法搞

可以贪心的想,一共k个集合的话,把k个集合连接起来需要k-1个新点,如果还有列没有,那就需要这些列需要新店除此之外,一开始没有讨论有些行压根没有点,这些行也需要点去开辟疆土

综上所述,一开始论述的时候将行和列交换也是合理的

人总喜欢在伤心,劳累,挫折时放纵自己,但这之后把你引向深渊

#include <algorithm>#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <queue>#include <set>#include <vector>using namespace std;typedef long long ll; const int N = 200005;const int INF = 0x3f3f3f3f;int f[N]; //colint find(int x) { return f[x] == x ? x : (f[x] = find(f[x])); }vector<int> row[N];vector<int> col[N];vector<int> part[N];int has[N];int tag[N];int main() { int n, m, q; while(~scanf("%d %d %d", &n, &m, &q)) { for(int i = 1; i <= m; ++i) f[i] = i; for(int i = 0; i < q; ++i) { int a, b; scanf("%d %d", &a, &b); row[a].push_back(b); tag[a] ++; col[b].push_back(a); has[b] = 1; } for(int i = 1; i <= n; ++i) { for(int j = 1; j < row[i].size(); ++j) { int t1 = row[i][0]; int t2 = row[i][j]; int f1 = find(t1); int f2 = find(t2); if(f1 != f2) { f[f2] = f1; } } } for(int i = 1; i <= m; ++i) { int tt = find(i); part[tt].push_back(i); } int cnt = 0; int cntPart = 0; for(int i = 1; i <= m; ++i) { if(!has[i]) continue; if(part[i].size() > 0) { cntPart ++; cnt += part[i].size(); } } int result = 0; for(int i = 1; i <= n; ++i) { if(!tag[i]) result ++; } // printf("%d", cnt); printf("%d", result + cntPart - 1 - cnt + m); } return 0;}

欢迎阅读本文章: 何女士

F66永乐国际官网欢迎您

F66永乐集团在线