这题的题意很明显，就是求MST然后每次改变一条边（只会变大），然后再求MST，在变下一条变之前，这条边又会变回原来的值，最后的答案就是每次的MST值除以改变的次数。
首先要先求MST，存图时要用邻接矩阵，因为是稠密图。。。
然后进行树形DP，这棵树要用已经求出的MST建立。当前节点为I，那么用f[i][j]表示以i为根的子树中到J点的距离最小值是多少，显然这个J不能是I的子树中的点，那么我们可以把一开始的邻接矩阵中a[i][i] 的值标记为-1，那么如果J为I子树中的点，一定有f[i][j] == -1，这样我们就可以进行转移了。
对q个查询，若改变的边是MST中的边，两端点为x、y，权值改为z，假设x为y的父亲，那么连接两断开子树的最短边就是y到x的祖先的边的最小值、y的子树（不包括y本身）到x的边的最小值、以及z的值中去最小，更新MST的值，累加。若改变的边不是MST中的边，那么直接累加MST的值。
附上代码。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #include<vector> 7 using namespace std; 8 const int N = 3010; 9 int d[N],f[N]; 10 bool v[N]; 11 int n,m,x,y,z; 12 int a[N][N]; 13 int dfn[N]; 14 int curr; 15 int b[N][N]; 16 int prim() 17 { 18 int tot = 0; 19 memset(d,63,sizeof(d)); 20 memset(v,0,sizeof(v)); 21 memset(f,0,sizeof(f)); 22 v[0] = 1; d[0] = 0; 23 for (int i = 1; i < n; i++) 24 { 25 d[i] = a[0][i]; 26 f[i] = 0; 27 } 28 for (int i = 1; i < n; i++) 29 { 30 int k = 0,minn = 1000000000; 31 for (int j = 0; j < n; j++) 32 if (!v[j] && d[j] < minn) 33 { 34 minn = d[j]; 35 k = j; 36 } 37 tot += d[k]; 38 //cout<<k<<" "<<d[k]<<" "<<tot<<endl; 39 v[k] = 1; 40 for (int j = 0; j < n; j++) 41 if (!v[j] && d[j] > a[k][j]) 42 { 43 d[j] = a[k][j]; 44 f[j] = k; 45 } 46 } 47 return tot; 48 } 49 void dfs(int x) 50 { 51 for (int i = 0; i < n; i++) 52 if (f[i] == x && a[x][i] < 1000000000 && a[x][i] != -1) 53 { 54 dfs(i); 55 for (int j = 0; j < n; j++) b[x][j] = min(b[x][j],b[i][j]); 56 } 57 for (int i = 0; i < n; i++) 58 if (i != f[x]) b[x][i] = min(b[x][i],a[x][i]); 59 } 60 int main() 61 { 62 while (scanf("%d%d",&n,&m) != EOF) 63 { 64 if (n == 0 && m ==0) break; 65 memset(a,63,sizeof(a)); 66 for (int i = 1; i <= m; i++) 67 { 68 scanf("%d%d%d",&x,&y,&z); 69 if (x != y) a[x][y] =a[y][x] = z; 70 } 71 int ans = prim(); 72 //for (int i = 0; i < n; i++) cout<<i<<" "<<dfn[i]<<endl; 73 memset(b,63,sizeof(b)); 74 for (int i = 0; i < n; i++) a[i][i] = -1; 75 //for (int i = 0; i < n; i++)cout<<i<<" "<<f[i]<<endl; 76 f[0] = -1; 77 //return 0; 78 dfs(0); 79 int q; 80 scanf("%d",&q); 81 long long sum = 0; 82 //cout<<ans<<endl; 83 for (int i = 0; i < q; i++) 84 { 85 scanf("%d%d%d",&x,&y,&z); 86 if (f[x] == y) 87 { 88 int minn = 1000000000; 89 sum = sum + ans; 90 sum -= a[x][y]; 91 for (int j = 0; j < n; j++) 92 if (j != y && b[x][j] != -1) minn = min(minn,b[x][j]); 93 for (int j = 0; j < n; j++) 94 if (f[j] == x && b[j][y] != -1) minn = min(minn,b[j][y]); 95 minn = min(minn,z); 96 sum += minn; 97 } 98 else if (f[y] == x) 99 { 100 int minn = 1000000000; 101 sum = sum + ans; 102 sum -= a[y][x]; 103 for (int j = 0; j < n; j++) 104 if (j != x && b[y][j] != -1) minn = min(minn,b[y][j]); 105 for (int j = 0; j < n; j++) 106 if (f[j] == y && b[j][x] != -1) minn = min(minn,b[j][x]); 107 minn = min(minn,z); 108 sum += minn; 109 } 110 else sum += ans; 111 } 112 double fin = sum; 113 fin = fin / q; 114 printf("%.4f\n",fin); 115 } 116 return 0; 117 }
POJ 4006 Genghis Khan the Conqueror,布布扣,bubuko.com
POJ 4006 Genghis Khan the Conqueror
原文：http://www.cnblogs.com/yuhao1994/p/3594842.html
