食物链
- Time Limit: 1000MS
- Memory Limit: 10000K
- Total Submissions: 85027
- Accepted: 25416
Description
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
Input
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。Output只有一个整数，表示假话的数目。
Sample Input
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
Sample Output
3
Source
题意
中文题面，意思很清晰。判断假话的数量。
题解
使用向量关系来维护并查集的合并更新操作。具体参考疯狂的小牛和讲解和驱动幽灵百鬼夜行小肆的讲解，非常详细。
假设有$x$和它的父节点$root[x]$，$relation[x]$表示$x$与$root[x]$的关系，$y$与$root[y]$同，（简写为$rel[x]$，$rel[y]$）
- relation[x] = 0，表示x与root[x]是同类
- relation[x] = 1，表示root[x]吃x
- relation[x] = 2，表示x吃root[x]
假设有向量$x \rightarrow y$（这里x为父节点，y为子节点）
- 当$x \rightarrow y$的偏移量为0，即rel[y] = 0时，x与y为同类
- 当$x \rightarrow y$的偏移量为1，即rel[y] = 1时，x吃y
- 当$x \rightarrow y$的偏移量为2，即rel[y] = 2时，y吃x
那么$x \rightarrow y$的偏移量就相当于题目中的$d-1$，$d=2$时$x$吃$y$，$d=1$时$x$和$y$为同类。
在进行合并操作时，我们把$root[y]$合并到$root[x]$上，让$root[x]$作为父节点，那么怎么更新它们之间的关系呢？这个时候，“向量”就派上了用场。
- $root[x] \rightarrow root[y] = root[x] \rightarrow x + x \rightarrow y + y \rightarrow root[y]$
- $rel[root[y]] = (rel[x] + (d - 1) + 3 - rel[y]) \% 3$
其中$\%3$为了保证结果在0到2之间，$y \rightarrow root[y]$的偏移值为$3 - rel[y]$。
在寻找根节点的路径压缩过程中$x$与其祖父节点$rootx[x]$之间的关系更新为$rel[x] = (rel[x] + rel[root[x]]) \% 3$
最后判断的时候，如果root[x]!=root[y]，则合并；如果相等，表明x与y的父亲是同一个，那么：
- 当d = 1时只需要判断rel[x]是否等于rel[y]
- 当d = 2时判断x和y之间的关系与前面已有的是否矛盾，$x \rightarrow y = x \rightarrow root[x] + root[x] \rightarrow y$，即$ (3 - rel[x] + rel[y]) \% 3 == d - 1$是否正确
具体实现看代码。
代码
- 版本一
| Status | Accepted |
|---|---|
| Time | 188ms |
| Memory | 4824kB |
| Length | 1354 |
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int F[maxn];
int rel[maxn];
int find(int x)
{
if (x == F[x])
return x;
int tmp = find(F[x]);
rel[x] = (rel[x] + rel[F[x]]) % 3;
F[x] = tmp;
return F[x];
}
int main()
{
int n, m, sum;
int d, x, y;
scanf("%d%d", &n, &m);
sum = 0;
for (int i = 1; i <= n; ++i)
{
F[i] = i;
rel[i] = 0;
}
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n)
{
sum++;
continue;
}
if (d == 2 && x == y)
{
sum++;
continue;
}
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty)
{
F[rooty] = rootx;
rel[rooty] = (rel[x] + d - 1 + 3 - rel[y]) % 3;
}
else
{
if (d == 1 && rel[x] != rel[y])
sum++;
else if (d == 2 && ((3 - rel[x] + rel[y]) % 3 != (d-1)))
sum++;
}
}
printf("%d\n", sum);
return 0;
}- 版本二
| Status | Accepted |
|---|---|
| Time | 195ms |
| Memory | 4824kB |
| Length | 2607 |
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int n, m, sum;
int d, x, y;
struct Node
{
int pre;
int rel;
}node[maxn];
void init()
{
for (int i = 0; i <= n; ++i)
{
node[i].pre = i;
node[i].rel = 0;
}
sum = 0;
}
int find(int x)
{
if (x == node[x].pre)
return x;
int tmp = node[x].pre;
node[x].pre = find(tmp);
node[x].rel = (node[x].rel + node[tmp].rel) % 3; // 更新子节点与祖宗的关系
return node[x].pre;
}
void merge(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx != fy)
{
node[fy].pre = fx; // 合并到fx
node[fy].rel = (node[x].rel + d - 1 + 3 - node[y].rel) % 3; // 更新关系
}
else
{
if (d == 1 && node[x].rel != node[y].rel) // 同类且父辈相同要求与父辈关系相同
sum++;
else if (d == 2 && ((3 - node[x].rel + node[y].rel) % 3 != (d - 1))) // 不同类判断是否符合关系d-1
sum++;
}
}
int main()
{
scanf("%d%d", &n, &m);
init();
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n) // 超过n
{
sum++;
continue;
}
if (d == 2 && x == y) // 同类自相残杀
{
sum++;
continue;
}
merge(x, y); // 合并
}
printf("%d\n", sum);
return 0;
}交的时候用了while(scanf("%d%d", &n, &m) == 2)和 while (~scanf("%d%d", &n, &m))竟然WA了！！！
找了一个小时的bug，
我还能说什么！！！
The end.
2018-04-19 星期四