首页 > 代码库 > HDU 1182 食物链

HDU 1182 食物链

2024-07-19 19:14:48   221人阅读

这是一道很有质量的并查集，做完这题我对并查集又有更深一步的理解了

题意：有编号1到N的A、B、C三类动物，满足A吃B，B吃C，C吃A

然后有K句话说

1 X Y:表示X和Y是同类

2 X Y:表示X吃Y

如果：X或者Y大于N，则是谎话。如果X吃X也是谎话。如果X和Y的关系能确定，并且和这句话给的X、Y的关系矛盾，那么也是谎话

否则这句话便是真话

我觉得这篇解题报告写得很好，里面的思路已经说得很详细了：

http://blog.csdn.net/ditian1027/article/details/20804911

 

X和Y无非就三种关系，每种关系用一个数表示，这并不稀奇。可厉害的是，在递推关系的时候居然能用统一的表达式表达出来，这就神了！Orz

说说我犯过的两点错误：

  1. 压缩路径的同时更新relation数组，开始我写的是
    parent[a] = GetParent(parent[a]);relation[a] = (relation[a] + relation[parent[a]]) % 3;

    问题在于，回溯的时候parent[a]已经被更新，也就不能用来计算了。所以用一个临时变量temp来暂存a之前的父节点

  2. 在合并X、Y的时候，要先找到X和Y所在树的树根px和py然后对两个树根进行合并，否则如果对x、y合并，会出现x和y的树根不等的情况。而且，根据x、y的关系以及和他们父节点的关系来推他们父节点的关系，这个表达式也真是不好想，真乃神人也！

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 50000 + 10; 8 int parent[maxn], relation[maxn]; 9 10 int GetParent(int a)11 {12     if(parent[a] == a)    return a;13     int temp = parent[a];14     parent[a] = GetParent(parent[a]);15     relation[a] = (relation[a] + relation[temp]) % 3;16     return parent[a];17 }18 19 int main(void)20 {21     #ifdef LOCAL22         freopen("1182in.txt", "r", stdin);23     #endif24 25     int n, k, r, x, y, cnt = 0;26     scanf("%d%d", &n, &k);27     memset(relation, 0, sizeof(relation));28     for(int i = 1; i <= n; ++i)29         parent[i] = i;30     while(k--)31     {32         scanf("%d%d%d", &r, &x, &y);33         if(x > n || y > n || (x==y && r==2))34         {35             ++cnt;36             continue;37         }38         GetParent(x);39         GetParent(y);40         if(parent[x] == parent[y])41         {42             if( (r==1 && relation[x]!=relation[y] )43                 ||(r==2 && (relation[x]+1)%3 != relation[y]) )44                 ++cnt;45         }46         else47         {48             int px = GetParent(x);49             int py = GetParent(y);50             parent[py] = px;51             relation[py] = ((relation[x]-relation[y] + 3) + (r - 1)) % 3;52         }53     }54     printf("%d\n", cnt);55     return 0;56 }
代码君

 

HDU 1182 食物链


联系
我们