问题传送门:
题目:
有三类动物A,B,C,三类动物的食物链构成了环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但并不知道底是哪一种。 有两种说法对 X 和 Y 两个动物的关系进行描述: "1 X Y",表示 X 和 Y 是同类。 "2 X Y",表示 X 吃 Y。
现在有 K 句描述,这 K 句话有的是真的,有的是假的。
- 当前的话与前面的某些真的话冲突,就是假话;
- 当前的话中 X 或 Y 比 N 大,就是假话;
- 当前的话表示 X 吃 X,就是假话。
N(1 <= N <= 50,000)(0 <= K <= 100,000),输出假话的总数。
分析:
首先不能用cin 输入,因为K太大了。 这是一道很经典的带权并查集,刚开始不知道这样做,想着用并查集 把每个物种放在一起。但是写不出来。~~~
带权并查集:不单单是储存了集合,而且还记录了集合中节点之间的关系。 更多的是记录每个节点与根节点之间的关系。 因为有路经压缩这个过程,把每个节点与根节点直接连接。 利用这个过程,计算出每个节点与根节点枝间的关系。 进而通过根节点,计算出集合中任意两个节点的关系。
对于这个题来说,任意两个节点之间只有三种关系: 同类,X吃Y,X被Y吃。可以用数字rel[i] 0 1 2 分别代表这三种关系。 然后用数组 rel[i] 来表示 i 到父节点的关系。 初始化时rel[i]=0; 表示自己和自己同类。 然后发现,当: 1 X Y d = 1, rel[x] = 0; 2 X Y d = 2, rel[x] = 1; (Y看作父节点) ~~rel[x] + 1 = d~~
判断真假话: 对于题目中的 2 与 3 条件直接判断,是假话就 res++; 重要的是对于条件 1: 当我们输入X, Y时,先分别求根节点
- 若两者根节点相同,说明已经赋予X,Y关系了,只需要判断题中给的关系 是否符合已有的关系即可:(根据向量关系)
$$则x到y的关系是:(3 + rel[x] -rel[y] ) % 3$$
2.若两者根节点不相同,说明我们还没有赋予x,y关系。把X和Y所在的子树合并。 这里有个细节问题,这里如果 r[ra] = rb,需要更新 ra 到 rb 的关系。 即更新 rel[ra]. 根据上面的公式,可以得出:
$$rel[a] + rel[ra] - rel[b] = d-1$$
$$rel[ra] = (d - 1 + rel[b] - rel[a] + 3) % 3$$
在路经压缩中更新关系: 要把每一个正确的值 与 根结点连接,用rel保存关系。 路经压缩是个递归的过程,在这个过程中,可以:
int t = r[x]; r[x] = Find(r[x]); rel[x] = (rel[x] + rel[t]) % 3;
递归更新关系。
代码:
#include <iostream> #include <cstdio> using namespace std; const int MAXN = 5e4+10; int r[MAXN]; int rel[MAXN]; void init(int n, int &res) { res = 0; for (int i = 1; i <= n; i++) r[i] = i, rel[i] = 0; } int Find(int x) { if (x == r[x]) return r[x]; else { int t = r[x]; r[x] = Find(r[x]); rel[x] = (rel[x] + rel[t]) % 3; return r[x]; } } bool Join(int d, int a, int b) { int ra = Find(a); int rb = Find(b); if (ra == rb) { if ((rel[a]-rel[b]+3)%3+1 != d) return false; else return true; } else { r[ra] = rb; rel[ra]=(d-rel[a]+rel[b]+3-1)%3; return true; } } int main() { int n, k, d, x, y, res; cin >> n >> k; init(n, res); for (int i = 0; i < k; i++) { scanf("%d %d %d",&d, &x, &y); if (d==2 && x==y) res++; else if (x>n || y>n) res++; else if(!Join(d, x, y))res++; } cout << res << endl; return 0; }
Comments | NOTHING