图论：最小瓶颈生成树

最小瓶颈生成树不一定是最小生成树，但最小生成树一定是最小瓶颈生成树

由于关心最大边便把边从小到大排序，最先生成的那棵生成树就是答案。而这就是Kruskal算法，所以原图的最小生成树就是一棵最小瓶颈生成树了

感觉这个解释很牵强呀

不过知道结论就舒服多了

题目是BZOJ2429

int kruskal()  //返回瓶颈 
{
    int tot=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+1+cnt,cmp);
    for(int i=1;i<=cnt;i++)
    {
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx!=fy)
        {
            fa[fx]=fy,tot++;
            if(tot==n-1) return e[i].w;
        }
    }
}

这里看一下返回的结果就知道了，返回的是瓶颈

然后直接计数就可以了

 1 #include<cstdio>
 2 #include<algorithm> 
 3 using namespace std;
 4 const int maxm=505;
 5 const int maxn=1005;
 6 int m,n,cnt,ans;
 7 int a[maxm],fa[maxn];
 8 struct Node{int x,y;}b[maxn];
 9 struct Edge{int u,v,w;}e[maxn*maxn/2];
10 bool cmp(Edge x,Edge y)
11 {
12     return x.w<y.w;
13 }
14 int read()
15 {
16     char c=getchar();
17     int x=0,t=1;
18     while(c>'9'||c<'0') {if(c=='-') t=-1;c=getchar();}
19     while(c<='9'&&c>='0') {x=x*10+(c-'0');c=getchar();}
20     return x*t;
21 }
22 int sqdist(int i,int j)
23 {
24     return (b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y);
25 }
26 int find(int x)
27 {
28     if(fa[x]!=x) fa[x]=find(fa[x]);
29     return fa[x];
30 }
31 int kruskal()  //返回瓶颈 
32 {
33     int tot=0;
34     for(int i=1;i<=n;i++) fa[i]=i;
35     sort(e+1,e+1+cnt,cmp);
36     for(int i=1;i<=cnt;i++)
37     {
38         int fx=find(e[i].u),fy=find(e[i].v);
39         if(fx!=fy)
40         {
41             fa[fx]=fy,tot++;
42             if(tot==n-1) return e[i].w;
43         }
44     }
45 }
46 int main()
47 {
48     m=read();
49     for(int i=1;i<=m;i++) a[i]=read();
50     n=read();
51     for(int i=1;i<=n;i++)
52         b[i].x=read(),b[i].y=read();
53     for(int i=1;i<=n;i++)
54         for(int j=i+1;j<=n;j++)
55         {
56             e[++cnt].u=i;e[cnt].v=j;
57             e[cnt].w=sqdist(i,j);
58         }
59     int mx=kruskal();
60     for(int i=1;i<=m;i++)
61         if(a[i]*a[i]>=mx) ans++;
62     printf("%d
",ans);
63     return 0;
64 }