苗条的生成树 Slim Span--洛谷

传送门

 

钢哥终于没给黑题紫题了（卑微v

稍稍需要多想一点点

--------------------------------------------------------------------------------------------------------

题意简述

求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

输入：

输入文件包含多组测试数据，每组测试数据如下： 第1行：2个整数n m （2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2），n表示顶点数，m表示边数。接下来m行，每行3个空格分开的整数a b w（1 ≤ w ≤ 10000） , 表示顶点a与顶点b之间有一条边，权值为w。

输出：

对每组测试数据，如果图存在生成树，输出生成树的差值最小的；否则，输出-1。

--------------------------------------------------------------------------------------------------------

由于n的值比较小

所以可以不用那种优化到极致的神仙算法/思路（可以小小的偷偷懒

把所有边按边权排序

从每个边求最小生成树

用最小生成树中的最大边权和最小边权的差来更新最终的ans

O（q*mlogm）

--------------------------------------------------------------------------------------------------------

最后有两个0 0方便退出询问

但是...也算是个小坑吧

--------------------------------------------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

inline int read()
{
    int sum = 0,p = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        (sum *= 10) += ch - '0';
        ch = getchar();
    }
    return sum * p;
}

const int INF = 99999;
int n,m,ans,maxns;
struct edge
{
    int frm,to,wei;
}e[5005];
int fa[105];

bool cmp(edge a,edge b)
{
    return a.wei < b.wei;
}

int findfa(int o)
{
    if(fa[o] == o)
        return o;
    else
        return fa[o] = findfa(fa[o]);
}

int kruskal(int o)
{
    int k = 0;
    maxns = -1;
    for(int i = 1;i <= n;i++)
        fa[i] = i;
    int minn = e[o].wei,maxn = 0;
    for(int i = o;i <= m;i++)
    {
        int a = findfa(e[i].frm);
        int b = findfa(e[i].to);
        if(a == b)
            continue;
        ++k;
        fa[a] = b;
        maxns = max(maxns,e[i].wei);
        if(k == n - 1)
            return 1;
    }
    return 0;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n == 0 && m == 0)
            return 0;
        ans = INF;
        memset(e,0,sizeof(e));
        memset(fa,0,sizeof(fa));
        for(int i = 1;i <= m;i++)
        {
            e[i].frm = read();
            e[i].to = read();
            e[i].wei = read();
        }
        sort(e+1,e+m+1,cmp);
        for(int i = 1;i <= m;i++)
        {
            if(kruskal(i))
                ans = min(ans,maxns - e[i].wei);
        }
        if(ans == INF)
            ans = -1;
        printf("%d\n",ans);
    }
    return 0;
}