P2024. 食物链

考点

• 边带权并查集

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 50;
int n, k, fa[LEN], val[LEN];

int find(int x) {
  if (fa[x] == x) return x;
  int anc = fa[x];
  fa[x] = find(fa[x]);
  val[x] = (val[x] + val[anc]) % 3;
  return fa[x];
}

void join(int x, int y, int w) {
  int a = find(x), b = find(y);
  fa[a] = b;
  val[a] = (val[y] + w - val[x] + 3) % 3;
}

int main() {
  int x, y, w, a, b, ans = 0;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  while (k--) {
    cin >> w >> x >> y;
    if (x > n || y > n || (w == 2 && x == y))
      ++ans;
    else {
      --w;
      a = find(x), b = find(y);
      if (a != b) {
        join(x, y, w);
      } else {
        if (w != (val[x] - val[y] + 3) % 3) ++ans;
      }
    }
  }
  cout << ans;
  return 0;
}

思路

边带权并查集的模板题

设边权表达式为\(X\xrightarrow{w}Y\)

• w等于0时，X和Y是同类
• w等于1时，X吃Y
• w等于2时，X被Y吃

边权表

举几个例子：

A(A对于B的关系)	B(B对于C的关系)	C(A对于C的关系)	含义
0	0	0	A、B同类，B、C同类，那么A、C也是同类
1	1	2	A吃B，B吃C，那么A被C吃
2	2	1	A被B吃，B被C吃，那么A吃C
1	0	1	A吃B，B、C同类，那么A吃C
0	1	1	A、B同类，B吃C，那么A吃C
2	0	2	A被B吃，B、C同类，那么A被C吃
0	2	2	A、B同类，B被C吃，那么A被C吃

可以发现，如果已知A -> B，B -> C，可得A -> C

边权表是编写边带权并查集的核心，只有关系能够递推与传递才有意义啊

路径压缩

如左图所示，B是A的父亲，C是A、B的祖先（所以中间画虚线）；右图则是路径压缩后的模样

可以发现，已知A -> B，B -> C，要求A -> C

这一操作在刚才的边权表已经计算过了，可以直接令val[x]为x结点到其祖先的边权

那么有

int B = fa[A];
...
//原本A->B的边权加上B->C的边权，就等于A->C的边权啦
val[A] = (val[A] + val[B]) % 3;

合并

两个集合合并时，只需要修改祖先结点的val值，因为子结点会在路径压缩的过程中更新

已知x和y的边权为w，要合并x和y所在的集合，只需要修改祖先a的val值

因为祖先a的祖先原本是自己，现在变成祖先b了

通过作图，可以得到

//内部加3是为了避免负数的出现
val[a] = (val[y] + w - val[x] + 3) % 3;