瓶颈生成树

瓶颈生成树

定义无向图G，G的瓶颈生成树是一棵 “ 树上最大边权值在G的所有生成树中最小 ” 的生成树，这样的生成树可能不止一棵。瓶颈生成树的值为树上最大边权值。

由瓶颈生成树的定义可知：最小生成树是瓶颈生成树的充分不必要条件，即最小生成树一定是瓶颈生成树，瓶颈生成树不一定是最小生成树。具体证明过程可以看这里：瓶颈生成树。

所以无向图的瓶颈生成树可以用最小生成树的算法去做。

最小生成树的模板题，那必然会有两大经典算法——Kruskal，Prim。不会的同学可以先看看这里：最小生成树Kruskal+Prim算法

例题：洛谷P1991 https://www.luogu.com.cn/problem/P1991

本题是是一道很裸的瓶颈生成树的题，由题可知一共有P个点就是树有P-1条边，有S个卫星电话就是不用连接最大的S-1条边，所以本题一共只需要树中前（P-S）条边里的最大边即可，剩下的边用卫星电话，即循环退出条件为合并边数为P-S，因为边的大小已经经过排序了，所以此时合并的边的权值就是瓶颈生成树的值。

AC代码如下：

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 using namespace std;
 4 const int N=1e6+5;
 5 int n,m,fa[N],cnt,a[N],b[N],t;
 6 double ans; 
 7 pair<double,pa> e[N];
 8 int f(int x)
 9 {
10     if(x==fa[x]) return x;
11     return fa[x]=f(fa[x]);
12 }//并查集
13 void kruskal()
14 {
15     for(int i=1;i<=n;i++) fa[i]=i;//初始化
16     sort(e+1,e+t+1);//排序
17     for(int i=1;i<=t;i++)
18     {
19         int u=e[i].second.first,v=e[i].second.second;
20         u=f(u);
21         v=f(v);
22         if(u!=v)
23         {
24             fa[u]=v;
25             ans=e[i].first;
26             cnt++;
27         }
28         if(cnt==n-m) break;//此时ans即为瓶颈生成树的值
29     }
30     printf("%0.2lf",ans);
31 }
32 int main()
33 {
34     cin>>m>>n;
35     for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
36     for(int i=1;i<n;i++)
37         for(int j=i+1;j<=n;j++)
38         {
39             //每两点之间先连一条边
40             double w=1.0*sqrt(1.0*(a[i]-a[j])*(a[i]-a[j])+1.0*(b[i]-b[j])*(b[i]-b[j]));
41             e[++t]=make_pair(w,make_pair(i,j));
42         }
43     kruskal();
44     return 0;
45 }