UVA1395-苗条的生成树-Slim-Span-题解

题目描述

(PDF)[https://onlinejudge.org/external/13/p1395.pdf]

题目翻译

求一个生成树，使它最大边减最小边之差最小

题解

我们暴力的生成多个生成树，然后取最小的最大边减最小边之差输出便可。

我们生成$m$次生成树，每进行第$i$次生成是我们要忽略$1 \sim i$的边。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

const int maxn  = 105;
int fa[maxn], n, m, tot, min = 99999999;

struct node
{
    int from, to, data;
    bool operator < (node &b) const
    {
        return data < b.data;
    }
} edge[10000];

int find(int x)
{
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

inline int kelusikale(int x)
{
    int num = 0, cnt = edge[x].data;
    for (register int i = x; i <= m; i++)
    {
        int xz = find(edge[i].from), yz = find(edge[i].to);
        if (xz != yz)
        {
            ++num;
            fa[xz] = yz;
        }
        if (num == n - 1)
        {
            return abs(cnt - edge[i].data);
            break;
        }
    }
    return -1;
}

int main()
{
    while (true)
    {
        min = 99999999;
        memset(fa, 0, sizeof fa);
        memset(edge, 0, sizeof edge);
        scanf("%d%d", &n, &m);
        if (n == 0 && m == 0)
            break;
        if (m == 0)
        {
            printf("-1\n");
            continue;
        }

        for (register int i = 1; i <= m; i++)
            scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].data);

        std::sort(edge + 1, edge + m + 1);
        for (register int j = 1; j <= m; j++)
        {
            for (register int i = 1; i <= n; i++)
                fa[i] = i;
            int x = kelusikale(j);
            if (x == -1 and j == 1)
            {
                min = -1;
                break;
            }
            else if (x == -1) x = 99999999;
            min = std::min(x, min);
        }
        printf("%d\n", min);
    }
}