算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    有三个物种 A,B,C,其中A可以吃B,B可以吃C,C可以吃A。 给出N(N<50000)个生物,给出X(X<100000)个定论,请问X个定论中有多少是谎话?

吐槽:

    刚做完GCJ想到"今天"还没有写题解,于是就坚持捉完了这个水题。可惜还是过了0点.... 残念啊

算法分析:

    除了正常的并查集需要记录每个节点的父亲以外,我们还要维护该点与父亲的关系(吃? 被吃? 等价?)
    判断的时候,如果i和j属于同一集合,这就不用说了....
    如果parent[i]!=parent[j],那么就将i和j所在集合合并,我的做法是将i的代表的父亲直接变为j。
    维护i与新的父亲j的关系只需要改变一下parent[i]与j的关系值就好了(i本身的关系值不必改变,因为i和parent[i]的关系在那里)。
    至于parent[i]和j的关系如何通过i和j的关系来确定.... 额 自己在纸上画一画就有了...
    
    路径压缩也要维护的(很重要)... 应该很简单吧.....
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define re1(i,n) for(int i=1;i<=n;i++)
 5 int P[50001][2];
 6 int find(int x){
 7     int u = P[x][0];
 8     if(u==x) return x;
 9     P[x][0]=find(u);
10     P[x][1]=(P[u][1] + P[x][1])%3;
11     return P[x][0];
12 }
13 int main(){
14     int n,k;
15     scanf("%d%d",&n,&k);
16         int c,a,b,ans=0;
17         re1(i,n) P[i][0] = i, P[i][1] = 0;
18         re1(i,k){
19             scanf("%d%d%d",&c,&a,&b);
20             if(a > n || b>n) { ans ++; continue;}
21             if(c == 1) {
22                 if(find(a)!=find(b)){
23                     int u = P[a][0];
24                     P[u][0] = b;
25                     P[u][1] = (3-P[a][1])%3;
26                 }
27                 else if(P[a][1]!=P[b][1]){
28                     ans ++;
29                 }
30             }
31             else {
32                 if(a == b) ans ++;
33                 else if(find(a)!=find(b)){
34                     int u = P[a][0];
35                     P[u][0] = b;
36                     P[u][1] = P[a][1]==2?2:P[a][1]^1;
37                 }
38                 else if((P[a][1]-P[b][1]+3) % 3 != 1) ans++;
39             }
40 //            re1(i,n) cout<<P[i][0]<<" "<<P[i][1]<<" ";cout<<endl;
41         }
42         cout<<ans<<endl;
43     
44 }
45 
posted on 2012-05-06 02:28 西月弦 阅读(379) 评论(7)  编辑 收藏 引用 所属分类: 解题报告经典题目

FeedBack:
# re: poj 1182 并查集
2012-06-04 23:26 | lenohoo
我的想法是对于一个编号为i的动物,其同时拥有两个元素i+n,i+2*n;
i+n 属于 吃 i 的集合,i+2*n属于被i吃 的 集合 ;
每次输入命令 , i , j ,
当命令为1时,如果出现find(i+n)==find(j) || find(i+2*n)==find(j)的情况,就出错;不然Union(i,j) , Union(i+n,j+n) , Union(i+2*n,j+2*n) ;
当命令为2时,如果出现find(i+2*n)==find(j) || find(i)==find(j)的情况,就出错;不然Union(i+n,j) , Union(i+2*n,j+n) , Union(i,j+2*n) ;
每次判断正误,但是错了,请问 是算法有问题吗?  回复  更多评论
  
# re: poj 1182 并查集
2012-06-05 10:22 | 西月弦
@lenohoo
是算法有问题
因为A吃B, B吃C,不代表A可以吃C 。。。  回复  更多评论
  
# re: poj 1182 并查集
2012-06-05 21:40 | lenohoo
@西月弦
因为a吃b,所以a+n和b在同一个集合,b吃c,b+n和c在同一个集合==>
a+2n和b+n和c在同一个集合,也就是a和c+n同一个集合,直接说明a被c吃了呀,不是吗?  回复  更多评论
  
# re: poj 1182 并查集
2012-06-06 10:26 | 西月弦
@lenohoo
我是说你理解错题意了 A吃B B吃C 就代表A吃C了么 ... 恰恰相反 应该是C吃A额...  回复  更多评论
  
# re: poj 1182 并查集
2012-06-06 16:14 | lenohoo
@西月弦
不是呀,根据上式,a吃b,b吃c,就直接能够推出c吃a了啊
  回复  更多评论
  
# re: poj 1182 并查集
2012-06-06 16:25 | 西月弦
@lenohoo
好高森... 没听懂.... 你可以拿我这个程序对拍去额... 或者用一种比较形式化的语言给我描述一下你的算法(邮件联系把)  回复  更多评论
  
# re: poj 1182 并查集
2012-06-06 16:50 | lenohoo
@西月弦
好的,谢谢大神  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理