HDU 5441

Problem Description

Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are

Input

The first line contains one integer

Output

You should print

Sample Input

1 5 5 3 2 3 6334 1 5 15724 3 5 5705 4 3 12382 1 3 21726 6000 10000 13000

Sample Output

2 6 12

n个城市,m条路,每条路有一个权值w; q个询问每次输入一个数temp,这个人可以走任何权值<=temp的路,
问这个人能走多少对城市 (城市(a,b)和(b,a)算两对); 就是算这个图有多少连通分量(不符合<=temp的边不加入图中),
对于每个连通分量,例如某连通分量有ABC三个城市,则有AB BA AC CA BC CB六个城市对;即有n个城市的连通分量
有n(n-1)个城市对;每个连通分量的城市数就是该集合根节点的秩(代码中的num[]数组);
计算结果时,每新加入一条边后的结果ans_now,可以由为加入该条边之前的结果ans递推得到;
例如两个连通分量的节点数为 fu ,fv;则join这两个连通分量后的结果ans_now=ans+(fu+fv)*(fu+fv-1)-fu*(fu-1)-fv*(fv-1)=2*fu*fv;

  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
",ans[i]);
107     }
108     return 0;
109 }

View Code

转自
https://blog.csdn.net/u013569304/article/details/48475251