洛谷 题解 UVA1395 【苗条的生成树 Slim Span】

【题意】

给出一个\(n(n<=100)\)个节点的的图，求最大边减最小边尽量小的生成树。

【算法】

\(Kruskal\)

【分析】

首先把边按边权从小到大进行排序。对于一个连续的边集区间\([L,R]\)，如果这些边使得\(n\)个点全部联通，则一定存在一个苗条度不超过\(W[R]-W[L]\)的生成树（其中\(W[i]\)表示排序后第\(i\)条边的权值）。

从小到大枚举\(L\)，对于每个\(L\)，从小到大枚举\(R\)，同时用并查集将新进入\([L,R]\)的边两端的点合并成一个集合，与\(Kruskal\)算法一样。当所有的点都联通是停止枚举\(R\)，换下一个\(L\)(并且把\(R\)重置为\(L\))，继续枚举。

【代码】

#include<bits/stdc++.h>

using namespace std;

const int MAXN=100+10;

const int MAXM=10000+10;

int n,m;

int fa[MAXN];

int maxn,ans=0x3f3f3f3f;

struct Node

{

    int u,v,w;

}edge[MAXM];

inline int read()

{

    int tot=0;

    char c=getchar();

    while(c<'0'||c>'9')

        c=getchar();

    while(c>='0'&&c<='9')

    {

        tot=tot*10+c-'0';

        c=getchar();

    }

    return tot;

}

inline bool cmp(Node x,Node y)

{

    return x.w<y.w;

}

inline int find(int k)//并查集

{

    if(fa[k]==k)return k;

    else return fa[k]=find(fa[k]);

}

inline bool kruskal(int k)//判断是否能形成生成树

{

    maxn=0;

    int tot=0;

    for(int i=1;i<=n;i++)

        fa[i]=i;

    for(int i=k;i<=m;i++)

    {

        if(fa[find(edge[i].u)]!=fa[find(edge[i].v)])

        {

            maxn=edge[i].w;

            fa[find(edge[i].u)]=fa[find(edge[i].v)];

            tot++;

        }

        if(tot==n-1)return 1;//如果所有点都联通，则返回true

    }

    return 0;//否则返回false

}

int main()

{

    while(1)

    {

        ans=0x3f3f3f3f;

        n=read();m=read();

        if(!n&&!m)break;

        for(int i=1;i<=m;i++)

        {

            edge[i].u=read();

            edge[i].v=read();

            edge[i].w=read();

        }

        sort(edge+1,edge+1+m,cmp);//给边进行从小到大排序

        for(int i=1;i<=m;i++)//枚举L

        {

            if(kruskal(i))

            {

                ans=min(ans,maxn-edge[i].w);//更新最小值

            }

        }

        if(ans!=0x3f3f3f3f)cout<<ans<<endl;

        else cout<<-1<<endl;//特判

    }

    return 0;

}

刘汝佳大法好！