UVA1395 苗条的生成树 Slim Span 题解

题目大意

给一个 $n$ 个点 $m$ 条边的图（$1 \le n \le 100,1 \le m \le \frac{n(n-1)}{2}$），求图的生成树中，最大边权减最小边权最小的生成树并输出这个差值。

分析

下面的分析绝对不是抄紫书的

按照一般求生成树的方法，我们都要将边按照边权从小到大排序，排完序后就能发现：如果最小的苗条度为 $W_r-W_l$ ，那么这个生成树的边一定在 $[l,r]$ 中。因为 $W_r$ 对应的边一定是边权最小的边， $W_l$ 对应的一定是边权最大的边，其他边的边权一定在两者之间，也就是在 $[l,r]$ 中。但是反过来，如果边都在 $[l,r]$ 中（目的是为了确定生成树的边的范围），只能说明苗条度不会超过 $W_r-W_l$（理由见上），这时就需要在加边时用变量保存边权最小的边和边权最大的边它们的编号了，最后如果确实能构成生成树，就更新 $ans$ 的值，苗条度用上面记下的编号能算出来。

既然用上述的方法的确能确定生成树的边和苗条度，那么从小到大枚举 $l$ 就行了，再从 $l$ 到 $m$ 枚举 $r$ ，再在 $[l,r]$ 范围内求生成树，每次更新 $ans$ 就没有了，注意判断环。部分代码：

void init(int &n) {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int Find(int x) {
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
bool Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y)
        return 0;
    fa[x] = y;
    return 1;
}
bool Kruskal(int &l, int &r) {
    init(n);
    int k = 0, wl, wr;//wl,wr见上文
    bool first = 1;
    for (int i = l; i <= r; i++) {
        if (Union(e[i].from, e[i].to)) {
            if (first)
                wl = i, first = 0;
            wr = i;
            //这么做不需要特判只有1条边的情况
            ++k;
        }
        if (k == n - 1)
            break;
    }
    if (k < n - 1)
        return 0;//如果有环返回false
    ans = std::min(ans, e[wr].w - e[wl].w);
    return 1;
}
ans=1<<30;
bool ok = 0;
        for (int l = 1; l <= m; l++)
            for(int r = l; r <=m; r++)
                if (Kruskal(l))
                    ok = 1;//能找到最小生成树
        if (!ok)
            puts("-1");
        else
            printf("%d\n", ans);

但是时间复杂度是 $O(n^3logn)$ 的，再加上多组数据，3s内过都很危险。代码中 $O(n^2)$ 枚举 $l,r$ ，$O(nlogn)$ 计算生成树。而当main函数中 $l$ 不变， $r$ 增加为 $r'$ 时，计算 $[l,r']$ 范围内的生成树多加了 $[l,r]$ 这条边，其实完全可以只加一次。所以只需要外层枚举 $l$ ，内层枚举 $r$ 时就算最小生成树，时间复杂度就是 $O(n^2logn)$ ，不会超时了。

完整代码

#include <cstdio>
#include <cstring>
#include <algorithm>
struct Edge {
    int from, to, w;
} e[4953];
bool cmp(Edge x, Edge y) {
    return x.w < y.w;
}
int n, m, fa[103], ans;
void init(int &n) {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int Find(int x) {
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
bool Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y)
        return 0;
    fa[x] = y;
    return 1;
}
bool Kruskal(int &l) {
    init(n);
    int k = 0, wl, wr;
    bool first = 1;
    for (int r = l; r <= m; r++) {//在这一层循环就计算生成树
        if (Union(e[r].from, e[r].to)) {
            if (first)
                wl = r, first = 0;
            wr = r;
            ++k;
        }
        if (k == n - 1)
            break;
    }
    if (k < n - 1)
        return 0;
    ans = std::min(ans, e[wr].w - e[wl].w);
    return 1;
}
int main () {
    while (scanf("%d%d", &n, &m) != EOF) {
        if (!n && !m)
            break;
        init(n);
        ans = 1 << 30;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].w);
        std::sort(e + 1, e + 1 + m, cmp);
        bool ok = 0;
        for (int l = 1; l <= m; l++)
            if (Kruskal(l))
                ok = 1;
        if (!ok)
            puts("-1");
        else
            printf("%d\n", ans);
    }
    return 0;
}