poj 1182 食物链(转)

本文主要是介绍poj 1182 食物链(转)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

*食物链，自己还是不会做，刚开始搞的太乱。后来网上看了看解题报告，认真看了一遍，
后来照自己开始写，几乎完成了全部，只是有一个判断真假的式子实在退步出来了，又看了
一眼，后来还是WA，于是把循环输入给改了才AC，看了大牛的思路，题是懂了，但是自己单
独就是编不上啊。。很郁闷。。
借鉴大牛然后自己总结了点思路：变种的并查集。其实这个还是两个元素之间的集合关系，
最后都要并在一个集合里，只不过，每类元素和根节点的关系不同(用r[x]表示的)，每次输入
两个元素后先判断是否会满足三个错误的条件，（2）项就是一般的比较，可以直接判断出，
（1）、（3）项要判断关系：如果他们已经合并，那么直接判断关系，就是那个式子。若没
有合并（根节点不同），直接合并就可以了，合并的时候比一般的并查集多了步骤，就是相互
关系的合并。 推出那三个式子很重要。find查找函数中的那个式子，要是我自己编，绝对想
不到的。。。
*/

 

#include "iostream" #include "stdio.h" using namespace std; int n,m; int p[50005],r[50005]; // r[x]表示x与p[x]的关系 ， 0为同类， 1为p[x]吃x, 2为x吃p[x]； int make() { int i; for(i=1; i<=n; i++) { p[i]=i; r[i]=0; } } int find(int x) { if(x!=p[x]) { int temp=p[x]; p[x]=find(p[x]); r[x]=(r[temp]+r[x])%3;//important. 更新r[]数组中x与代表元素的相对关系。更新原因:代表元素在 //union_set操作中被改变了。至于这个式子的推得.可以枚举rx与p[x], p[x] //与x的关系，然后观察得到。更好的方法是向量运算。来自poj 1182 Discuss } return p[x]; } int Union(int x,int y,int d) { int rx,ry; rx=find(x),ry=find(y); p[ry] = rx; r[ry] = ( r[x] - r[y] + 2 + d ) % 3; //此处要根据那个类似于动态方程的东西来做 由于是要把y并在x里 // 所以要分析r[x]、x、y三者的关系来列式 } int main() { int i,j,d,x,y; int ry,rx,fls; scanf("%d%d",&n,&m); fls=0; make(); for(i=1; i<=m; i++) { scanf("%d%d%d",&d,&x,&y); if(x>n||y>n||(d==2&&x==y)) { fls++; continue; } rx=find(x),ry=find(y); if(rx==ry) { if(d==1 && r[x]!=r[y]) { fls++;continue; } else { if(d==2 && r[x] != (r[y]+2)%3) fls++; } } else Union(x,y,d); } printf("%d/n",fls); system("pause"); return 0; } /*食物链，自己还是不会做，刚开始搞的太乱。后来网上看了看解题报告，认真看了一遍， 后来照自己开始写，几乎完成了全部，只是有一个判断真假的式子实在退步出来了，又看了 一眼，后来还是WA，于是把循环输入给改了才AC，看了大牛的思路，题是懂了，但是自己单 独就是编不上啊。。很郁闷。。 借鉴大牛然后自己总结了点思路：变种的并查集。其实这个还是两个元素之间的集合关系， 最后都要并在一个集合里，只不过，每类元素和根节点的关系不同(用r[x]表示的)，每次输入 两个元素后先判断是否会满足三个错误的条件，（2）项就是一般的比较，可以直接判断出， （1）、（3）项要判断关系：如果他们已经合并，那么直接判断关系，就是那个式子。若没 有合并（根节点不同），直接合并就可以了，合并的时候比一般的并查集多了步骤，就是相互 关系的合并。 推出那三个式子很重要。find查找函数中的那个式子，要是我自己编，绝对想 不到的。。。 */

 

另外，我的做法来自http://www.360doc.com/content/10/0816/19/2692170_46550429.shtml 上面挺全的，大家要看看。

 

另附原题，方便直接看题,

 

Description

Input

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

这篇关于poj 1182 食物链(转)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---