ICPC archive 6187 并查集

https://icpcarchive.ecs.baylor.edu

因为给你的是两物品的重量差，问你的也是两物品的重量差，所以，如果告诉你两物品的重量差，这就相当于给你一种等价关系，把两物品所在的集合合并，并能推导出合并完的集合内所有的物品的差，为了加速该过程，可以在每个子结点记录自己与父结点的重量差，然后在查找时路径压缩，让结点的父结点直接是根结点，重量差就要更新，这步要做对，自己推导推导怎么做，然后在合并两集合时采用启发式合并，说白了就是把结点数少的那个集合作为结点数多的集合的子结点。这样操作会少一些。

贴代码：

View Code

  1 #include <cstdio>
  2 #define MAXN 100005
  3 int n;
  4 struct point
  5 {
  6     int pre,w;
  7 } p[MAXN];
  8 int cnt[MAXN];
  9 int find(int x)
 10 {
 11     int s = x;
 12     int cur = 0;
 13     while(p[s].pre > 0)
 14     {
 15         cnt[cur++] = p[s].w;
 16         s = p[s].pre;
 17     }
 18     for(int i = cur-1;i > 0; i--)
 19     cnt[i-1] = cnt[i]+cnt[i-1];
 20     cur= 0 ;
 21     while(s != x)
 22     {
 23         point  tmp = p[x];
 24         p[x].pre = s;
 25         p[x].w = cnt[cur++];
 26         x = tmp.pre;
 27     }
 28     return s;
 29 }
 30 void UFset(int x,int y,int w)
 31 {
 32     int s;
 33     int r1 = find(x);
 34     int r2 = find(y);
 35     if(r1 == r2) return ;
 36     int total = p[r1].pre + p[r2].pre;
 37     if(p[r1].pre > p[r2].pre)
 38     {
 39         int t1 = w;
 40         s = y;
 41         while(p[s].pre > 0)
 42         {
 43             t1 += p[s].w;
 44             s = p[s].pre;
 45         }
 46         s = x;
 47         int t2 = 0;
 48         while(p[s].pre > 0)
 49         {
 50             t2 += p[s].w;
 51             s = p[s].pre;
 52         }
 53         p[r1].pre = r2;
 54         p[r1].w = t1-t2;
 55         p[r2].pre = total;
 56     }
 57     else
 58     {
 59         int t1 = -w;
 60         s = x;
 61         while(p[s].pre > 0)
 62         {
 63             t1 += p[s].w;
 64             s = p[s].pre;
 65         }
 66         s = y;
 67         int t2 = 0;
 68         while(p[s].pre > 0)
 69         {
 70             t2 += p[s].w;
 71             s = p[s].pre;
 72         }
 73         p[r2].pre = r1;
 74         p[r2].w = t1-t2;
 75         p[r1].pre = total;
 76     }
 77 }
 78 void computer(int x,int y)
 79 {
 80     int t1 = find(x);
 81     int t2 = find(y);
 82     if(t1 != t2)
 83     {
 84         printf("UNKNOWN\n");
 85         return ;
 86     }
 87     printf("%d\n",p[x].w-p[y].w);
 88 }
 89 int main()
 90 {
 91 //    freopen("in1.cpp","r",stdin);
 92     int m;
 93     int x,y,w;
 94     char a[3];
 95     while(~scanf("%d%d",&n,&m))
 96     {
 97         if(n == 0 && m == 0)  break;
 98         for(int i=1; i<=n; i++)
 99         {
100             p[i].pre = -1;
101             p[i].w = 0;
102         }
103         while(m--)
104         {
105             scanf("%s",a);
106             if(a[0] == '!')
107             {
108                 scanf("%d%d%d",&x,&y,&w);
109                 UFset(x,y,w);
110             }
111             else
112             {
113                 scanf("%d%d",&x,&y);
114                 computer(x,y);
115             }
116         }
117     }
118     return 0;
119 }