无向图，保证每两点之间最多有一条直接相连的边（这题保证的东西还挺多的），然后Q次更新，每次增加某条边的权值（每次更新都是作用在初始的图上），求出本次的mst值，最后求平均。

所以问题就是根据每次更新的边以及原始mst求最新mst。两种情况：

• 更新边不是原始mst上的。所以还是原始mst的值。
• 更新边是原始mst上的。则要么mst的结构不变，要么这条边被一条不属于原始mst的边替换。

一点一点来分析为什么。

1. 首先，考虑 “在必须不要一条mst边的情况下，怎么快速组织新的mst?”
   在原始mst中考虑，每条边都可以看作是连接两个连通分量的桥，去掉每条边，原始mst就一分为二了。
   设某条mst边连接的两个连通分量的点数分别为n1,n2，则原图（假设无重边）中最多（要看原图是否有这些边，有可能一条都没有）有n1*n2-1条边都可以替换这条mst边！其中边权最小的边就是原mst边的最佳替换边。
   （本质就是选第二小）

2. 为什么用一条非mst边替换就完事了？为什么其他mst边都不用变？为什么不需要重新求mst?
   反证法。若其他mst边还有更好的选择，那原始mst怎么不去选？

3. 然而。mst边不一定有最佳替换边（一条替换边都没有）。
   就算有最佳替换边，回归这道题本身，如果mst边的更新值还是比最佳替换边小，那么还是选mst边。

上述道理说明白了。然而，具体在求最佳替换边的时候并不这么求，而是反向考虑：每条非mst边可以替换哪些mst边。
可以想到，每条非mst边在mst中形成了一个环，这条非mst边仅可以替换该环上的mst边。为什么？反证法。
虽然可以替换，但是这只能说明该环上mst边的替换边集合内都有这条非mst边，并不意味着它可以作为最佳替换边。

正好边表已经被排序过了，于是依次让每条非mst边访问一下自己的这个环（dfs实现），只用标记那些没有被标记过的边就行了。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <utility>
using namespace std;const int INF = 1e9;
const int MAXN = 3000;
int N, M, Q;struct Edge
{int n1, n2, w;bool operator<(const Edge& e) const{return w < e.w;}
};
vector<Edge> ve;
vector<pair<int, int>> v[MAXN];
int mst;
int conn;
int pre[MAXN];int rep[MAXN][MAXN];                  // mst边的最佳替换边（不一定有）的权值
int counter;                          // 记录有多少mst边有最佳替换边
double total;bool in_mst[MAXN][MAXN];              // 因为它查询的时候直接给边的两点，所以要这样存，不能放在ve里面
int g[MAXN][MAXN];                    // 这玩意儿不用初始化// 注意这几个二维数组都不区分方向，所以赋值的时候...
void init()
{ve.clear();                       // 调错10分钟for (int i = 0; i < N; i++)v[i].clear();mst = 0;conn = 0;memset(pre, -1, sizeof pre);memset(rep, -1, sizeof rep);counter = 0;total = 0;memset(in_mst, 0, sizeof in_mst);
}int f(int x)
{if (pre[x] < 0) return x;return pre[x] = f(pre[x]);
}bool u(int n1, int n2)
{int f1 = f(n1);int f2 = f(n2);if (f1 != f2){conn++;if (pre[f1] <= pre[f2]){pre[f1] += pre[f2];pre[f2] = f1;}else{pre[f2] += pre[f1];pre[f1] = f2;}return true;}return false;
}bool dfs(int n, int f, int w, int prev)               // n是当前走到的点，f是终点，prev是n的前驱点
{if (n == f) return true;for (int i = 0; i < v[n].size(); i++){if (v[n][i].first != prev)                    // 不走回头路{if (dfs(v[n][i].first, f, w, n))          // 表示已经找到到终点的路  {if (rep[n][v[n][i].first] == -1){rep[n][v[n][i].first] = rep[v[n][i].first][n] = w;counter++;}return true;                          // 只要找到了，就可以回溯返回上一层了，因为这样的路仅此一条！}}}return false;
}int main()
{int a, b, c;for (; ~scanf("%d%d", &N, &M);){if (N == 0 && M == 0) break;                  // 这题说结束标志了吗？init();for (int i = 0; i < M; i++){scanf("%d%d%d", &a, &b, &c);ve.push_back({ a,b,c });g[a][b] = g[b][a] = c;}sort(ve.begin(), ve.end());for (int i = 0; i < ve.size(); i++){if (u(ve[i].n1, ve[i].n2)){mst += ve[i].w;in_mst[ve[i].n1][ve[i].n2] = in_mst[ve[i].n2][ve[i].n1] = true;v[ve[i].n1].push_back(make_pair(ve[i].n2, ve[i].w));v[ve[i].n2].push_back(make_pair(ve[i].n1, ve[i].w));    // 邻接表只加mst上的边}if (conn == N - 1) break;}for (int i = 0; i < ve.size(); i++){if (!in_mst[ve[i].n1][ve[i].n2])                // 从非mst边出发，找那个环{dfs(ve[i].n1, ve[i].n2, ve[i].w, -1);if (counter == N - 1) break;                // 如果算够了就提前退出}                                               // 然而有可能某些mst边都没有替换边，也就没有最佳替换边了}scanf("%d", &Q);for (int i = 0; i < Q; i++){scanf("%d%d%d", &a, &b, &c);if (in_mst[a][b])                               // 所谓最佳替换边也不一定要用，还要和原mst上的边的最新值比较一下看谁更小  {if (rep[a][b] == -1) rep[a][b] = INF;       // 重点来了！！调错2个小时      等于-1说明该边没有替换边！！！total += mst - g[a][b] + min(c, rep[a][b]);}else total += mst;}printf("%.4f\n", total / Q);                        // total是double，存得下}return 0;
}