好题，学到了很多新姿势。
题意：在一棵mst上，修改一些边的值（此边有可能不在MST上），Q次操作（每次只是在原图上修改），求修改后的MST总和.
题解：首先Prim 求出MST （n^2）
对于每次修改，即相当于把MST上一条边截掉,原来的MST变成了两棵树，可以证明修改后的新MST一定包含这两棵树，，也就是说只需要找到连接两棵树的最短边即可。
好了，关键问题就是怎样找连接两棵树上的最短边。可以用（n^2）的dp进行预处理，然后每次o（1）查询即可。
我们用dp[i][j] 表示 树A（包含i的树） 到 树B（包含j的树）的最短边长。类似floyd的更新处理。具体看代码。
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<cmath>using namespace std;const int N = 3000 + 10;const int inf = 1e8;vector<int> ed[N];vector<int> son[N];typedef long long ll;ll map[N][N],sum;int fa[N],dis[N],pre[N],n,m,u,v,w,q;int dp[N][N];void prim(){sum = 0;for(int i=1;i<=n;i++) ed[i].clear();int now=1,min_p,min_dis;for(int i=1;i<=n;i++) dis[i] = inf;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(now != j &&dis[j] > 0 && map[now][j] < dis[j]){dis[j] = map[now][j];pre[j] = now;}}min_p = -1; min_dis = inf;dis[now] = -1;for(int j=1;j<=n;j++) if(dis[j] > 0 && dis[j] < min_dis){min_p = j;min_dis = dis[j];}if(min_p==-1) break;ed[min_p].push_back(pre[min_p]);ed[pre[min_p]].push_back(min_p);now = min_p;sum += min_dis;}}void bbu(int x,int pa){for(int i=0;i<ed[x].size();i++) if(ed[x][i]!=pa){son[x].push_back(ed[x][i]);fa[ed[x][i]] = x;bbu(ed[x][i],x);}}void build(){for(int i=1;i<=n;i++) fa[i] = i;for(int i=1;i<=n;i++) son[i].clear();bbu(1,0);}//注意下面的更新ll dfs(int p,int u,int fa) //求p到 u及u的子树的最短边{ll ans = inf;for(int i=0;i<ed[u].size();i++) if(ed[u][i]!=fa){int v = ed[u][i];int tmp = dfs(p,v,u);ans = min(ans,(ll)tmp);dp[u][v] = dp[v][u] = min(dp[u][v],tmp);}if(p != fa)ans = min(ans,map[p][u]);return ans;}void init(){for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=inf;for(int i=1;i<=n;i++)dfs(i,i,-1);}int main(){while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0) break;double ans = 0.0;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j] = inf ;for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);u++; v++;map[u][v] = map[v][u] = w;}for(int i=1;i<=n;i++) map[i][i] = 0;prim();build();init();scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%d%d%d",&u,&v,&w);u++;v++;int fl = 1;if(fa[u]!=v && fa[v]!=u) fl=0;if(fl==0)ans += sum;elseans += sum – map[u][v] + min(w , dp[u][v]);}printf("%.4f\n",ans/q);}return 0;}
但我们好多人没想过，勇敢的冷静的理智的去接受失败，
