HDU 4126 Genghis Khan the Conqueror

题意：
给你n个点，m条边的图，有Q次询问，每次询问输入u,v,w,表示将u->v的边权替换成w后（w一定不小于替换前的值），最小生成树的权值和为多少，求Q次询问的平均值（替换只在当前询问有效）

---

题解：
可以先处理出MST，考虑每次替换的边是否在MST中，首先如果不在MST中肯定是最简单的，MST的权值和不变，所以我们只需要考虑添加的边在MST中的情况。容易想到，如果在MST中，那么将这条边删掉就会形成两颗子树，所以我们要找的就是将这两颗子树重新连接起来的最小边。直接对每个点都dfs一次，求出删除u->v边重新连接的边中有一个点为tag的最小边长就可以了

---

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
const int INF = 0x3f3f3f3f;
int n,m,Q,pre[MAXN],dis[MAXN][MAXN],dp[MAXN][MAXN],vis[MAXN][MAXN];
struct node{ int u,v,w; }edge[MAXN*MAXN];
vector<int> g[MAXN];
inline bool cmp(node x,node y){ return x.w<y.w; }
int Find(int x){ return pre[x]==x ? pre[x]:pre[x]=Find(pre[x]); }
inline int Kruskal(){
	int res=0,cnt=0;
	for(int i=0;i<m;i++){
		int xx=Find(edge[i].u),yy=Find(edge[i].v),w=edge[i].w;
		if(xx!=yy){
			cnt++; res+=w; pre[xx]=yy;
			vis[edge[i].u][edge[i].v]=vis[edge[i].v][edge[i].u]=1;
			g[edge[i].u].push_back(edge[i].v);
			g[edge[i].v].push_back(edge[i].u);
		}
		if(cnt==n-1) return res;
	}
	return res;
}
int dfs(int u,int fa,int tag){
	int res=INF;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		int mi=dfs(v,u,tag);
		res=min(res,mi); dp[u][v]=dp[v][u]=min(dp[u][v],mi);
	}
	if(fa!=tag) res=min(res,dis[tag][u]);
	return res;
}
signed main(){
	while(~scanf("%d%d",&n,&m)){
		if(n==0 && m==0) return 0;
		for(int i=0;i<n;i++) pre[i]=i,g[i].clear();
		for(int i=0;i<n;i++) for(int j=0;j<n;j++) dis[i][j]=dp[i][j]=INF,vis[i][j]=0;
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
			dis[edge[i].u][edge[i].v]=dis[edge[i].v][edge[i].u]=edge[i].w;
		}
		sort(edge,edge+m,cmp);
		int MST=Kruskal();
		for(int i=0;i<n;i++) dfs(i,-1,i);
		scanf("%d",&Q); double res=0;
		for(int i=0;i<Q;i++){
			int u,v,w; scanf("%d%d%d",&u,&v,&w);
			if(!vis[u][v] && !vis[v][u]) res+=MST;
			else res+=MST-dis[u][v]+min(w,dp[u][v]);
		}
		printf("%.4f\n",res/Q);
	}
	return 0;
}