[小資料版]邊權內插補點最小的生成樹

題目

小 s 最近學了最小生成樹，不過聰明的小 s 顯然對簡單的求最小生成樹不感興趣。現在小 s 想知道，對于一個給定的圖，它的所有生成樹中，最大邊和最小邊的邊權差最小是多少.

題解

kruscal模闆？？

因為根據Kruskal算法的原理，最小生成樹的最短邊确定後，最長邊也相應确定，他們的內插補點就确定（參見《算法導論》）。是以可以枚舉最短邊求出生成樹。

僅限小資料。

code

/*
   oooooooo         o       o      o              o     ooooo      o            o                  ooooo            oooooooo           ooooooo
   oo      o         o     o       oo            oo       o        o            o                 o     o           o      o           o
   oo      o          o   o        o o          o o       o        o            o                o       o          o      o           o
   oooooooo            o o         o  o        o  o       o        o            o               o         o         oooooooo           o
   oo                   o          o   o      o   o       o        o            o               o         o         o                  ooooooo
   ooooooooooo          o		   o    o    o    o       o        o            o               o         o         o                  o
   oo         o         o          o     o  o     o       o        o            o                o       o          o                  o     
   oo         o         o          o      oo      o       o        o            o                 o     o           o                  o
   ooooooooooo          o          o       o      o     ooooo      oooooooooo   oooooooooo         ooooo            o                  ooooooo
*/

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>    
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

typedef long long ull;
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    return s * w;
}

int n;
int m;
int u;
int v;
int w;
int ans;
int f[maxn];
struct Tree {
    int from ,to, dis;
    bool operator <(const Tree &t) const {
        return dis < t.dis;
    } 
}t[maxn];

namespace handle {
    inline void clear() {
        ans = inf;
        memset(f, 0, sizeof(f));
        memset(t, 0, sizeof(t));
    }
    inline void reset() {
        for (int i = 1; i <= n; ++i) f[i] = i;
    }
    inline int find(int k) {
        return f[k] == k ? k : f[k] = find(f[k]);
    }
}

void kru(int k) {
    handle::reset();
    int cnt = 0, kmin = inf, kmax = -1; 
    for (int i = k; i <= m; ++i) {
        int u = handle::find(t[i].from), v = handle::find(t[i].to);
        if (u != v) {
            f[u] = v;
            // printf("%d %d \n", u, f[t[i].from]);
            kmax = std::max(kmax, t[i].dis);
            kmin = std::min(kmin, t[i].dis);
            ++cnt;
        }
    }
    if (cnt == n - 1) {
        ans = std::min(ans, abs(kmax - kmin));
    }
}

int main() {
    handle::clear();
    handle::reset();
    n = read(); m = read();
    for (int i = 1; i <= m; ++i) {
        u = read(), v = read(), w = read();
        t[i].from = u; t[i].to = v; t[i].dis = w;
    }
    std::sort(t + 1, t + m + 1);
    for (int i = 1; i <= m - n + 1; ++i) kru(i);
    if (ans == inf) printf("-1\n");
    else printf("%d\n", ans);
    // system("PAUSE");
    return 0;
}