图论：最小瓶颈路

最小瓶颈路的意思是已经告诉你起点和终点了然后让你求瓶颈，最小瓶颈生成树呢是让你求出连通所有点的

所以最小瓶颈路求起来更快

例题UVA534

double kruskal(int u,int v)
{
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int x=e[i].u,y=e[i].v;
        int fx=find(x),fy=find(y);
        if(fx!=fy)
        {
            fa[fx]=fy;
            if(find(u)==find(v)) return e[i].w;
        }
    }
}

然后加入有T组询问，你就要提前预处理出所有的

这个方法在求次小生成树的代码里有体现，直接抄过来就好了

本质上是预处理出f数组

然后给出完整的实现：

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 const int INF=0x7f7f7f7f;
 6 const int maxn=205;
 7 const int maxm=20005;
 8 int n,m;
 9 int fa[maxn];
10 struct Node{int x,y;}a[maxn];
11 struct Edge{int u,v;double w;}e[maxm];
12 bool cmp(Edge x,Edge y){return x.w<y.w;}
13 double dist(int i,int j)
14 {
15     return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
16 }
17 int find(int x)
18 {
19     if(fa[x]!=x) fa[x]=find(fa[x]);
20     return fa[x];
21 }
22 double kruskal(int u,int v)
23 {
24     for(int i=1;i<=n;i++) fa[i]=i;
25     sort(e+1,e+m+1,cmp);
26     for(int i=1;i<=m;i++)
27     {
28         int x=e[i].u,y=e[i].v;
29         int fx=find(x),fy=find(y);
30         if(fx!=fy)
31         {
32             fa[fx]=fy;
33             if(find(u)==find(v)) return e[i].w;
34         }
35     }
36 }
37 int main()
38 {
39     int T=0;
40     while(scanf("%d",&n)!=EOF&&n)
41     {
42         m=0;
43         for(int i=1;i<=n;i++)
44             scanf("%d%d",&a[i].x,&a[i].y);
45         for(int i=1;i<=n;i++)
46             for(int j=i+1;j<=n;j++)
47             {
48                 e[++m].u=i;e[m].v=j;
49                 e[m].w=dist(i,j);
50             }    
51         printf("Scenario #%d
Frog Distance = %.3lf

",++T,kruskal(1,2));
52     }
53     return 0;
54 }