HDU 5441

  1 #include <iostream>
  2 #include <bits/stdc++.h>
  3 #define MAX 30005
  4 #define foi1(n) for(int i=0;i<n;i++)
  5 using namespace std;
  6 
  7 struct node
  8 {
  9     int u,v;
 10     int w;
 11 }st[1000005];
 12 
 13 struct nod
 14 {
 15     int val;
 16     int id;
 17     friend bool operator<(nod a,nod b)
 18     {
 19         return a.val<b.val;
 20     }
 21 }qu[5005];
 22 
 23 bool cmp(node a,node b)
 24 {
 25     return a.w<b.w;
 26 }
 27 int father[20005];
 28 int num[20005];
 29 void initial(int n)
 30 {
 31     int i;
 32     for(i=1;i<=n;++i)
 33     {
 34         father[i]=i;
 35         num[i]=1;
 36     }
 37 }
 38 int find(int x)
 39 {
 40     int t=x;
 41     while(x!=father[x])
 42         x=father[x];
 43     while(t!=father[t])
 44     {
 45         int temp=t;
 46         t=father[t];
 47         father[temp]=x;
 48     }
 49     return x;
 50 }
 51 void hy(int x,int y)
 52 {
 53     x=find(x);
 54     y=find(y);
 55     if(x!=y)
 56     {
 57         father[y]=x;
 58         num[x]+=num[y];
 59     }
 60 }
 61 int ans[6000];
 62 int main()
 63 {
 64     int T;
 65     scanf("%d",&T);
 66     while(T--)
 67     {
 68         int n,m,q;
 69         scanf("%d%d%d",&n,&m,&q);
 70         int i;
 71         for(i=1;i<=m;++i)
 72         {
 73             scanf("%d%d%d",&st[i].u,&st[i].v,&st[i].w);
 74         }
 75         sort(st+1,st+m+1,cmp);
 76         for(i=1;i<=q;++i)
 77         {
 78             scanf("%d",&qu[i].val);
 79             qu[i].id=i;
 80         }
 81         sort(qu+1,qu+q+1);
 82         int t=1;
 83         initial(n);
 84         int s=0;
 85         for(i=1;i<=q;++i)
 86         {
 87             int temp;
 88             temp=qu[i].val;
 89             while(t<=m&&st[t].w<=temp)
 90             {
 91                 int u=st[t].u;
 92                 int v=st[t].v;
 93                 int x=find(u);
 94                 int y=find(v);
 95                 if(x!=y)
 96                 {
 97                     s+=2*num[x]*num[y];//叠加计算总的
 98                  hy(u,v);
 99                  /*我想的是用插入边之后的根节点对应的num来计算s=num*（num-1），一直WA，可能是因为在插边后根节点不止一个？？？*/
100                 }
101                 t++;
102             }
103             ans[qu[i].id]=s;
104         }
105         for(i=1;i<=q;++i)
106             printf("%d\n",ans[i]);
107     }
108     return 0;
109 }