http://poj.org/problem?id=1703这道题我写了没有多久,但是无端的MLE了很久,很多人不想看我唠叨,所以我还是开始说说这道题.
我天真的以为他给我的两个囚犯会在不同集合中,当然如果你不理解这道题,我说这个你还是不懂...
不好意思..我比较水..不要喷我.现在才说.
思路:
仅仅维护一个大的集合,这道题和poj1182的思路一样,不过写起来可以说更简单一点.我们把提供给我们的关系,全部都放到一颗树(一个集合)上面,而不是所谓的两个集合,那么关系呢?如何记录呢?就是我们不光维护我们的爸爸是什么,还要维护我们和爸爸的关系,和爸爸在同一个囚犯组织,or not. 然后每次添加新元素的时候一定要注意判断(这两个元素是不是在同一个集合中,这个是非常的重要的,否则会出现无限递归的情况,然后MLE.也就是我刚开始说的..天真的以为..),添加的时候举个例子,在纸上画画.x 的爸爸是 p, x的值可能为0or1,0为同一个阵营,1为不同的阵营,而y与x不同阵营且一共两个阵营,所以知道 v[x]=1--->v[y]=0,v[x]=1--->v[y]=1 ====> v[y]=(v[x]+1)%2; 然后就是询问了,找到根,然后判断两个值是否相等即可,原因就是都和同一个父亲比较那么值相同则同类(如果你要问我为什么是和同一个父亲比较,我告诉你..你回去学并查集,然后学路径压缩,然后会发现他们都在一个父亲下面).
code:
1 #include<iostream>
2 #include<cstdio>
3 const int N = 100002;
4 using namespace std;
5 #define REP(i,from,to) for(int i=(from);i<=(to);++i)
6 struct disset{
7 int *d,*v,l;
8 disset(int *d,int *v,int l):d(d),v(v),l(l){
9 REP(i,1,l){
10 d[i]=i;
11 v[i]=0;
12 }
13 }
14 int find(int x){
15 int u = d[x];
16 if(u!=x){
17 d[x] = find(u);
18 v[x] = (v[x] + v[u])%2;
19 }
20 return d[x];
21 }
22 void diff(int x,int y){
23 int u = find(x);
24 d[u] = y;
25 v[u] = (v[x]+1) % 2;
26 }
27 };
28 int a[N],v[N];
29 struct disset *s ;
30 int work(char c,int x,int y){
31 int ux = s->find(x);
32 int uy = s->find(y);
33 if(c=='A'){
34 if(ux!=uy)
35 return 0;
36 else{
37 if(v[x]==v[y])
38 return 2;
39 else
40 return 1;
41 }
42 }
43 else{
44 if(ux!=uy)
45 s->diff(x,y);
46 }
47 return -1;
48 }
49 int main(){
50 int ccase;
51 scanf("%d",&ccase);
52 while(ccase--){
53 int n,m;
54 scanf("%d%d",&n,&m);
55 s = new struct disset(a,v,n);
56 while(m--){
57 char c[2];
58 int x,y;
59 scanf("%s%d%d",c,&x,&y);
60 int ans = work(c[0],x,y);
61 // REP(i,1,5)
62 // cout<<a[i]<<' '<<v[i]<<'|';
63 // cout<<endl;
64 if(ans==0)
65 printf("Not sure yet.\n");
66 else if(ans==1)
67 printf("In different gangs.\n");
68 else if(ans==2)
69 printf("In the same gang.\n");
70 }
71 delete s;
72 }
73 return 0;
74 } 做到后来发现还有一道题..原来是我少见多怪了...其实都是并查集大水题..2492,也是poj上面的代码如下:
code:
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define REP(i,from,to) for(int i=(from);i<=(to);++i)
5 struct disset{
6 int *d,*v,l;
7 disset(int *d,int *v,int l):d(d),v(v),l(l){
8 REP(i,1,l){
9 d[i]=i;
10 v[i]=0;
11 }
12 }
13 bool is_same(int x,int y){
14 return v[x]==v[y];
15 }
16 int find(int x){
17 int u = d[x];
18 if(u!=x){
19 d[x] = find(u);
20 v[x] = (v[x]+v[u])%2;
21 }
22 return d[x];
23 }
24 void add(int x,int y){
25 int u = find(x);
26 d[u] = y;
27 v[u] = ( v[x] + 1 )%2;
28 }
29 }*s;
30 bool work(int x,int y){
31 int ux = s->find(x);
32 int uy = s->find(y);
33 if(ux==uy){
34 if(s->is_same(x,y))
35 return false;
36 }
37 else{
38 s->add(x,y);
39 }
40 return true;
41 }
42 const int N = 100002;
43 int a[N],v[N];
44 int main(){
45 int tcase;
46 scanf("%d",&tcase);
47 REP(ccase,1,tcase){
48 printf("Scenario #%d:\n",ccase);
49 bool ans=true;
50 int n,ttcase;
51 scanf("%d%d",&n,&ttcase);
52 s = new struct disset(a,v,n);
53 while(ttcase--){
54 int x,y;
55 scanf("%d%d",&x,&y);
56 if(!work(x,y))
57 ans = false;
58 }
59 delete s;
60 if(!ans)
61 printf("Suspicious bugs found!\n\n");
62 else
63 printf("No suspicious bugs found!\n\n");
64
65 }
66 }
posted on 2012-07-09 22:49
Gin 阅读(625)
评论(0) 编辑 收藏 引用 所属分类:
Data Structure