当前位置: 代码迷 >> 综合 >> 【NOI2001】食物链
  详细解决方案

【NOI2001】食物链

热度:83   发布时间:2023-12-13 22:32:19.0

题目链接:https://www.luogu.org/problemnew/show/P2024

此题主要考脑洞和并查集,我们可以建立三个集合(存在一个数组中),分别表示自身,捕食,天敌。接下来只需要按照题目中所给的错误提示进行判断即可。这里主要说下冲突的情况,即对于x和y,若它们是同类(即为1时),则x的天敌一定不与y同类,x的捕食也一定不与y同类,若没有发生冲突,就按照x和y,x的捕食和y的捕食,x的天敌和y的天敌合并即可。为2的情况时,也同样推理x和y的关系,然后推理合并的结果即可。

code:

#include<iostream>
using namespace std;const int N = 1e6;
int n, k, ans;
int f[N];void init() {int i;for (i = 1; i <= n*3; i++)f[i] = i;return ;
}int find(int u) {if (f[u] == u) return f[u];else return f[u] = find(f[u]); 
}void merge(int x, int y) {int fx = find(x), fy = find(y);if (fx != fy) f[fy] = fx;return ;
}int main() {cin >> n >> k;init();int i, op, x, y;for (i = 1; i <= k; i++) {cin >> op >> x >> y;if (x>n || y>n) {ans++;continue;}if (op == 1) {if (find(n+x)==find(y) || find(2*n+x)==find(y)) {ans++;continue;}merge(x, y), merge(n+x, n+y), merge(2*n+x, 2*n+y);}if (op == 2) {if (x == y || find(x)==find(y) || find(2*n+x) == find(y)) {ans++;continue;}merge(x+n, y), merge(x, 2*n+y), merge(2*n+x, n+y);}}cout << ans;return 0;
}