hdu4750Count The Pairs（最小生成树找瓶颈边）

 1 /*
 2    题意：就是给你一个图，图的每两个点都有多条路径，每一条路径中都有一条最大边，
 3    所有最大边的最小边（也就是瓶颈边）就是这两点之间的val值！然后给你一个值f，
 4    问有多少个顶点对的val>=f! (u,v) 和 (v, u)是不同的顶点对！
 5 
 6    思路：最小生成树（kruskral）那么每两个节点(u,v)的瓶颈边就是这一棵树中u到v
 7          的路径中的最大边值！
 8          在利用并查集的过程中，A, B两个集合，如果有u属于A，v属于B，且u-v可以将
 9          A-B集合连接起来，因为边值由小到大选取，那么以u-v边为瓶颈边的节点的个数
10          就是[A]*[B]*2;
11 
12    注意：图不一定是连通的，开始的时候当成了一棵树，怎么改都不对！
13 */
14 #include<iostream>
15 #include<cstring>
16 #include<cstdio>
17 #include<algorithm>
18 #define N 10105
19 #define M 500105
20 using namespace std;
21 int f[N];
22 struct Edge{
23     int u, v, w;
24     Edge(){}
25     Edge(int u, int v, int w){
26         this->u=u;
27         this->v=v;
28         this->w=w;
29     }
30 };
31 
32 Edge edge[M];
33 int dist[N];
34 int rank[N];
35 int cnt[N];
36 int edgeN;
37 int sumN[N];
38 int n, m;
39 
40 bool cmp(Edge a, Edge b){
41    return a.w < b.w;
42 }
43 
44 int getFather(int x){
45    return x==f[x] ? x : f[x]=getFather(f[x]);
46 }
47 
48 bool Union(int a, int b){
49    a=getFather(a); 
50    b=getFather(b);
51    if(a!=b){
52       cnt[++edgeN]=sumN[a]*sumN[b]*2;//记录以这一条边为瓶颈边的节点对的个数
53       if(rank[a]>rank[b]){
54           f[b]=a;
55           sumN[a]+=sumN[b];//将b集合放入到a集合中去
56       }
57       else{
58          f[a]=b;
59          sumN[b]+=sumN[a];//将a集合放入到b集合中去
60          ++rank[b];
61       }
62       return true;
63    }
64    return false;
65 }
66 
67 void Kruskral(){
68    edgeN=0;
69    sort(edge, edge+m, cmp);
70    for(int i=1; i<=n; ++i)
71       f[i]=i, rank[i]=0, sumN[i]=1;
72    for(int i=0; i<m; ++i)
73     if(Union(edge[i].u, edge[i].v))
74        dist[edgeN]=edge[i].w;//记录最小生成树中的边值
75    cnt[edgeN+1]=0;
76    for(int i=edgeN; i>=1; --i)//统计大于等于第i条边为瓶颈边边值的所有节点对的对数
77        cnt[i]+=cnt[i+1];
78 }
79 
80 int main(){
81     int p;
82     while(scanf("%d%d", &n, &m)!=EOF){
83         for(int i=0; i<m; ++i){
84            int u, v, w;
85            scanf("%d%d%d", &u, &v, &w);
86            edge[i]=Edge(u+1, v+1, w);
87         }
88         Kruskral();
89         scanf("%d", &p);
90         while(p--){
91            int x;
92            scanf("%d", &x);
93            int index=lower_bound(dist+1, dist+edgeN+1, x)-dist;
94            if(index>edgeN) printf("0\n");
95            else printf("%d\n", cnt[index]);
96         }
97     }
98     return 0;
99 }

//如果最后只有一棵树的话，这样做就可以了！没想到可能不是仅仅一棵树

1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define N 10105
 6 #define M 500105
 7 using namespace std;
 8 int f[N];
 9 struct Edge{
10     int u, v, w;
11     Edge(){}
12     Edge(int u, int v, int w){
13         this->u=u;
14         this->v=v;
15         this->w=w;
16     }
17 };
18 
19 Edge edge[M];
20 int dist[N];
21 int rank[N];
22 int cnt[N];
23 int edgeN;
24 
25 int n, m;
26 
27 bool cmp(Edge a, Edge b){
28    return a.w < b.w;
29 }
30 
31 int getFather(int x){
32    return x==f[x] ? x : f[x]=getFather(f[x]);
33 }
34 
35 bool Union(int a, int b){
36    a=getFather(a); 
37    b=getFather(b);
38    if(a!=b){
39       if(rank[a]>rank[b])
40           f[b]=a;
41       else{
42          f[a]=b;
43          ++rank[b];
44       }
45       return true;
46    }
47    return false;
48 }
49 
50 void Kruskral(){
51    edgeN=0;
52    sort(edge, edge+m, cmp);
53    for(int i=1; i<=n; ++i)
54       f[i]=i, rank[i]=0;
55    for(int i=0; i<m; ++i)
56      if(Union(edge[i].u, edge[i].v))
57         dist[++edgeN]=edge[i].w;
58    cnt[edgeN+1]=0;
59    for(int i=edgeN; i>=1; --i){
60        cnt[i]=i*2;
61        cnt[i]+=cnt[i+1]; 
62    }
63 }
64 
65 int main(){
66     int p;
67     while(scanf("%d%d", &n, &m)!=EOF){
68         for(int i=0; i<m; ++i){
69            int u, v, w;
70            scanf("%d%d%d", &u, &v, &w);
71            edge[i]=Edge(u+1, v+1, w);
72         }
73         Kruskral();
74         scanf("%d", &p);
75         while(p--){
76            int x;
77            scanf("%d", &x);
78            int index=lower_bound(dist+1, dist+edgeN+1, x)-dist;
79            if(index>edgeN) printf("0\n");
80            else printf("%d\n", cnt[index]);
81         }
82     }
83     return 0;
84 }