HDU

題目大意：有N個點，M條路，現在給出K條路，這K條路是在M條路中將權值擴大的路。每給出一條，就要求求出最小生成樹的權值
現在問每條路的最小生成樹的權值和/K的最小值是多少

解題思路：先得到最小生成樹，然後判斷路是不是最小生成樹的樹邊，如果不是，就不影響了
如果是的話，就要判斷一下是不是要去掉該邊，再添加新的邊。
如果去掉該邊的話，就相當於把最小生成樹劃分成了兩個塊，所以現在需要的是一條最小邊來連接兩個塊
我們設dp[u][v]為u到 v和到以v為根的樹的所有點的最小權值(以v為根就相當於有一條樹邊的一個結點是v的邊斷了，然後分成了兩個塊，而u和v在不同的塊)，這個可以通過dfs得到
得到這個了，那就可以得到每條樹邊斷後，需要添加的最小權值邊了，也是通過dfs得到

#include 
#include 
#include 
using namespace std;

#define N 3010
#define ll long long
const int INF = 1000000000;

int n, m, tot;
int dis[N][N], best[N][N], d[N], f[N], dp[N][N];
bool vis[N];
vector G[N];

void init() {
    memset(dis, 0x3f, sizeof(dis));
    int u, v, c;
    for (int i = 0; i < m; i++) {
        scanf(%d%d%d, &u, &v, &c);
        dis[u][v] = dis[v][u] = c;
    }
}


ll prim() {
    memset(vis, 0, sizeof(vis));
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        d[i] = dis[0][i];
        f[i] = 0;
        G[i].clear();
    }
    d[0] = INF;
    f[0] = -1;
    vis[0] = true;

    for (int i = 0; i < n - 1; i++) {
        int x = 0;
        for (int j = 1; j < n; j++)
            if (!vis[j] && d[j] < d[x])
                x = j;

        vis[x] = true;
        ans += d[x];

        if (f[x] != -1) {
            G[x].push_back(f[x]);
            G[f[x]].push_back(x);
        }

        for (int j = 1; j < n; j++) 
            if (!vis[j] && d[j] > dis[x][j]) {
                d[j] = dis[x][j]; 
                f[j] = x;
            }
    }
    return ans;
}

//得到dp[u][v]
int dfs1(int u, int fa, int root) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa) 
            dp[root][u] = min(dp[root][u], dfs1(v, u, root));
    }
    if (fa != root) dp[root][u] = min(dp[root][u], dis[root][u]);
    return dp[root][u];
}

//得到樹邊斷裂後需要的最小權值邊
int dfs2(int u, int fa, int root) {
    int ans = dp[u][root];
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa) ans = min(ans, dfs2(v, u, root));
    }
    return ans;
}

void solve() {
    memset(dp, 0x3f, sizeof(dp));
    ll MinTreeValue = prim();
    double ans = 0;
    for (int i = 0; i < n; i++)
        dfs1(i, -1, i);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < G[i].size(); j++) {
            int v = G[i][j];
            best[i][v] = best[v][i] = dfs2(v, i, i); 
        }
    int u, v, c, q;
    scanf(%d, &q);
    for (int i = 0; i < q; i++) {
        scanf(%d%d%d, &u, &v, &c);
        if (f[u] != v && f[v] != u) 
            ans += MinTreeValue * 1.0;
        else
            ans += MinTreeValue * 1.0 - dis[u][v] + min(best[u][v], c);
    }

    printf(%.4f
, ans / q);
}

int main() {
    while (scanf(%d%d, &n, &m) != EOF && n + m ) {
        init();
        solve();
    }
    return 0;
}