<span>周更2（并查集）</span>

1. POJ - 1308 Is It A Tree?

题意：给你一堆点队，问能否组成一棵树。

题解：如果两个点有相同的祖宗或对于这个图有不止一个根节点，则这不是一棵树，否则是一颗树。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 int par[1001000];
 7 
 8 int find(int x)
 9 {
10 
11     while(x!=par[x]) x=par[x];
12     return x;
13 
14 }
15 
16 void  unionn(int x,int y)
17 {
18     int fa=find(x);
19     int fb=find(y);
20     if(fa!=fb) par[fa]=fb;
21 }
22 
23 int main()
24 {
25     int n,m;
26     int t=1;
27     while(1){
28         int flag=0;
29         memset(par,0,sizeof (par));
30         while(scanf("%d%d",&n,&m)&&n&&m){
31             if(n==-1&&m==-1) return 0;
32             if(!par[n]) par[n]=n;if(!par[m]) par[m]=m;
33             if(find(n)==find(m)) flag=1;    //两点在同一个并查集内
34             if(!flag) unionn(n,m);
35         }
36         int ans=0;
37         for(int i=1;i<10010;i++)
38             if(par[i]==i) ans++;      //不止一颗树
39         if(flag||ans>1) printf("Case %d is not a tree.\n",t++);
40         else printf("Case %d is a tree.\n",t++);
41     }
42     return 0;
43 }

View Code

2. POJ - 2912 Rochambeau

题意：给出n个人石头剪刀布的结果，问哪个人是裁判，裁判可以随便瞎出，不影响比赛结果。

题解：暴力枚举裁判，判断当此人是裁判时，结果会不会出现矛盾，没有出现矛盾，此人就是裁判；出现矛盾则说明此人不是裁判。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 int par[10010];
 7 int d[10100];
 8 struct node
 9 {
10     int a,b;
11     char c;
12 }p[10010];
13 
14 int find(int x)
15 {
16     int t=par[x];
17     if(t!=x){
18         par[x]=find(par[x]);
19         d[x]=(d[x]+d[t])%3;
20     }
21     return par[x];
22 }
23 
24 int unionn(int x,int y,int z)
25 {
26     int fa=find(x);
27     int fb=find(y);
28     if(fa==fb) {
29         if((d[x]-d[y]+3)%3!=z) return 1;
30     }
31     else{
32         par[fa]=fb;
33         d[fa]=(d[y]-d[x]+z+3)%3;
34     }
35     return 0;
36 }
37 
38 int main()
39 {
40     int n,m;
41     while(scanf("%d%d",&n,&m)!=EOF){
42         int gg=0,k,flag=1,sum=0;
43         memset(p,0,sizeof p);
44         if(m==0) {printf("Player 0 can be determined to be the judge after 0 lines\n");continue;}
45         for(int i=1;i<=m;i++){
46             scanf("%d%c%d",&p[i].a,&p[i].c,&p[i].b);
47         }
48         for(int i=0;i<n;i++){
49             flag=1;
50             for(int j=0;j<n;j++)
51                 par[j]=j,d[j]=0;
52             for(int j=1;j<=m;j++){
53                 int z;
54                 if(p[j].a==i||p[j].b==i) continue;
55                 if(p[j].c=='=') z=0;
56                 else if(p[j].c=='<') z=2;
57                 else if(p[j].c=='>') z=1;
58                 if(unionn(p[j].a,p[j].b,z)){
59                     flag=0;
60                     gg=max(gg,j);
61                     break;
62                 }
63             }
64             if(flag){
65                 k=i;
66                 sum++;
67             }
68         }
69         if(sum>1) printf("Can not determine\n");
70         else if(!sum) printf("Impossible\n");
71         else printf("Player %d can be determined to be the judge after %d lines\n",k,gg);
72     }
73     return 0;
74 }

View Code

3. POJ - 1984 Navigation Nightmare

题意:给出多对点和两点之间的位置关系，然后给出一系列询问，表示在第几个关系给出后询问某两点的曼哈顿距离，如果距离未知则输出-1。

题解：把位置坐标分为x轴和y轴，所以有两个权值，x[i]记录i的x轴到其根节点x轴的距离，y[i]记录i的y轴到其根节点y轴的距离，（压缩路径和合并集合时权值的改变类似于向量的加减），把询问离线存储再判断。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<math.h>
 5 using namespace std;
 6 
 7 int par[1010000];
 8 
 9 struct node
10 {
11     int u,v,w;
12     char f;
13 }p[1001000];
14 
15 int xx[100100],yy[100100];
16 
17 int find(int x)
18 {
19     int t=par[x];
20     if(x!=par[x]) {
21         par[x]=find(par[x]);
22         xx[x]+=xx[t];
23         yy[x]+=yy[t];
24     }
25     return par[x];
26 }
27 
28 void unionn(int num)
29 {
30     int u=p[num].u;
31     int v=p[num].v;
32     char f=p[num].f;
33     int fa=find(u);
34     int fb=find(v);
35     if(fa==fb) return ;
36     par[fa]=fb;
37     xx[fa]=xx[v]-xx[u];
38     yy[fa]=yy[v]-yy[u];
39     if(f=='N') yy[fa]-=p[num].w;
40     if(f=='W') xx[fa]+=p[num].w;
41     if(f=='S') yy[fa]+=p[num].w;
42     if(f=='E') xx[fa]-=p[num].w;
43 }
44 
45 int main()
46 {
47     int n,m;
48     scanf("%d%d",&n,&m);
49     for(int i=1;i<=n;i++){
50         par[i]=i;
51         xx[i]=0,yy[i]=0;
52     }
53     for(int i=0;i<m;i++){
54         scanf("%d%d%d %c",&p[i].u,&p[i].v,&p[i].w,&p[i].f);
55     }
56     int t;
57     scanf("%d",&t);
58     int st=0;
59     while(t--){
60         int x,y,z;
61         scanf("%d%d%d",&x,&y,&z);
62         for(int i=st;i<z;i++){
63             unionn(i);
64         }
65         st=z;
66         int fa=find(x);
67         int fb=find(y);
68         if(fa!=fb) printf("-1\n");
69         else printf("%d\n",abs(xx[x]-xx[y])+abs(yy[x]-yy[y]));
70     }
71     return 0;
72 }

View Code

4. POJ - 1456 Supermarket

题意：有N件商品，价格为p，保质期为d。只能在保质期之前卖出去，并且每天只能卖出一个。求最大的利润。

题解：先安排价格高的商品，最好是放在保质期d那一天，如果已经被占了就往前找（类似并查集找祖宗的过程）。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<iostream>
 5 #include<string.h>
 6 using namespace std;
 7 
 8 struct node
 9 {
10     int a,b;
11 }p[1001000];
12 
13 int vis[1000100];
14 
15 int cmp(node x,node y)
16 {
17     if(x.a==y.a) return x.b>y.b;
18     return x.a>y.a;
19 }
20 
21 int main()
22 {
23     int n;
24     while(scanf("%d",&n)!=EOF){
25         memset(vis,0,sizeof vis);
26         memset(p,0,sizeof p);
27         for(int i=0;i<n;i++){
28             scanf("%d%d",&p[i].a,&p[i].b);
29         }
30         sort(p,p+n,cmp);
31         int sum=0;
32         for(int i=0;i<n;i++){
33             int j=p[i].b;
34             while(vis[j]&&j>0) j--;
35             if(j==0) continue;
36             if(!vis[j]) sum+=p[i].a,vis[j]=1;
37         }
38         printf("%d\n",sum);
39     }
40     return 0;
41 }

View Code