HDU 4750 Count The Pairs(并查集）

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 #define LL __int64
  8 int o[10001],rank[10001];
  9 struct node
 10 {
 11     int u,v,w;
 12 } edge[500001];
 13 int n,m;
 14 int que[500001];
 15 LL ans[500001];
 16 bool cmp(node a,node b)
 17 {
 18     return a.w < b.w;
 19 }
 20 int find(int x)
 21 {
 22     int r,t;
 23     r = x;
 24     while(x != o[x])
 25         x = o[x];
 26     while(r != x)
 27     {
 28         t = o[r];
 29         o[r] = x;
 30         r = t;
 31     }
 32     return x;
 33 }
 34 void merge(int x,int y)
 35 {
 36     x = find(x);
 37     y = find(y);
 38     if(x != y)
 39     {
 40         o[x] = y;
 41         rank[y] += rank[x];
 42     }
 43 }
 44 int bin(int x)
 45 {
 46     int str,end,mid;
 47     str = 0;
 48     end = m-1;
 49     if(x > que[end])
 50         return m;
 51     while(str < end)
 52     {
 53         mid = (str+end)/2;
 54         if(que[mid] < x)
 55             str = mid + 1;
 56         else
 57             end = mid;
 58     }
 59     return str;
 60 }
 61 int main()
 62 {
 63     int i,u,v,t;
 64     LL sum;
 65     while(scanf("%d%d",&n,&m)!=EOF)
 66     {
 67         for(i = 0;i < n;i ++)
 68         {
 69             rank[i] = 1;
 70             o[i] = i;
 71         }
 72         for(i = 0; i < m; i ++)
 73         {
 74             scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
 75             que[i] = edge[i].w;
 76             ans[i] = 0;
 77         }
 78         sort(que,que+m);
 79         sort(edge,edge+m,cmp);
 80         sum = 0;
 81         for(i = 0; i < m; i ++)
 82         {
 83             u = find(edge[i].u);
 84             v = find(edge[i].v);
 85             if(u != v)
 86             {
 87                 ans[i] = (LL)rank[u] * rank[v]*2;
 88                 sum += (LL)rank[u] * rank[v]*2;
 89                 merge(u,v);
 90             }
 91         }
 92         for(i = 1;i < m;i ++)
 93         ans[i] = ans[i] + ans[i-1];
 94         scanf("%d",&t);
 95         for(i = 0; i < t; i ++)
 96         {
 97             scanf("%d",&u);
 98             v = bin(u);
 99             if(v == 0)
100                 printf("%I64d\n",sum);
101             else
102                 printf("%I64d\n",sum-ans[v-1]);
103         }
104     }
105     return 0;
106 }