题意分析

1. 问题背景：哲别将军需要在城市之间设置守卫，使得所有城市之间能够安全通信，且总成本最小。由于可能发生起义，某一条道路的成本会增加，需要计算起义后的期望最小总成本。
2. 初始问题：这是一个典型的最小生成树（MST）问题，目标是选择一组道路使得所有城市连通且总成本最小。
3. 起义影响：起义会随机选择一条可疑道路，将其成本增加到更高的值。需要计算所有可疑情况下新 MST 的平均成本。

解题思路

1. 初始 MST：使用 Kruskal 或 Prim 算法计算初始的最小生成树及其总成本。
2. 处理可疑道路：
   • 对于每条可疑道路 $(X_i, Y_i, C_i)$，检查它是否在初始 MST 中。
   • 如果在初始 MST 中，则替换这条道路可能会增加总成本；需要重新计算 MST。
   • 如果不在初始 MST 中，则起义不会影响当前 MST，总成本不变。
3. 期望计算：对所有可疑情况的新 MST 成本取平均值。

C++代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 3010;
int d[N],f[N];
bool v[N];
int n,m,x,y,z;
int a[N][N];
int dfn[N];
int curr;
int b[N][N];
int prim()
{
    int tot = 0;
    memset(d,63,sizeof(d));
    memset(v,0,sizeof(v));
    memset(f,0,sizeof(f));
    v[0] = 1; d[0] = 0;
    for (int i = 1; i < n; i++)
    {
        d[i] = a[0][i];
        f[i] = 0;
    }
    for (int i = 1; i < n; i++)
    {
        int k = 0,minn = 1000000000;
        for (int j = 0; j < n; j++)
            if (!v[j] && d[j] < minn)
        {
            minn = d[j];
            k = j;
        }
        tot += d[k];
       //cout<<k<<" "<<d[k]<<" "<<tot<<endl;
        v[k] = 1;
        for (int j = 0; j < n; j++)
            if (!v[j] && d[j] > a[k][j])
        {
            d[j] = a[k][j];
            f[j] = k;
        }
    }
    return tot;
}
void dfs(int x)
{
    for (int i = 0; i < n; i++)
        if (f[i] == x && a[x][i] < 1000000000 && a[x][i] != -1)
    {
        dfs(i);
        for (int j = 0; j < n; j++) b[x][j] = min(b[x][j],b[i][j]);
    }
    for (int i = 0; i < n; i++)
    if (i != f[x]) b[x][i] = min(b[x][i],a[x][i]);
}
int main()
{
    while (scanf("%d%d",&n,&m) != EOF)
    {
        if (n == 0 && m ==0) break;
        memset(a,63,sizeof(a));
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if (x != y) a[x][y] =a[y][x] = z;
        }
        int ans = prim();
        //for (int i = 0; i < n; i++) cout<<i<<" "<<dfn[i]<<endl;
        memset(b,63,sizeof(b));
        for (int i = 0; i < n; i++) a[i][i] = -1;
        //for (int i = 0; i < n; i++)cout<<i<<" "<<f[i]<<endl;
        f[0] = -1;
        //return 0;
        dfs(0);
        int q;
        scanf("%d",&q);
        long long sum = 0;
        //cout<<ans<<endl;
        for (int i = 0; i < q; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if (f[x] == y)
            {
                int minn = 1000000000;
                sum = sum + ans;
                sum -= a[x][y];
                for (int j = 0; j < n; j++)
                if (j != y && b[x][j] != -1) minn = min(minn,b[x][j]);
                for (int j = 0; j < n; j++)
                if (f[j] == x && b[j][y] != -1) minn = min(minn,b[j][y]);
                minn = min(minn,z);
                sum += minn;
            }
            else if (f[y] == x)
            {
                int minn = 1000000000;
                sum = sum + ans;
                sum -= a[y][x];
                for (int j = 0; j < n; j++)
                if (j != x && b[y][j] != -1) minn = min(minn,b[y][j]);
                for (int j = 0; j < n; j++)
                if (f[j] == y && b[j][x] != -1) minn = min(minn,b[j][x]);
                minn = min(minn,z);
                sum += minn;
            }
            else sum += ans;
        }
        double fin = sum;
        fin = fin / q;
        printf("%.4f\n",fin);
    }
    return 0;
}