本文主要是介绍2016 Multi-University Training Contest 1-1001---HDU 5723 Abandoned country(DFS+最小生成树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：HDU 5723
题意：给出一些点及其之间的一些边的权值，求最小生成树的总权值以及任意两点之间路径权值的期望。
题解：最小生成树用Kruskal算法求出。
求期望，先求出在每两点之间路径权值的总和，除以C(n,2)即可。
求总权值，在最小生成树中，每条边都可以将树分成两部分，也就是分成的两部分中的点之间的路径中必定包含该边，所以这条边的贡献度为边两边点数相乘然后乘以边的权值，即为该边的贡献度，DFS遍历求出总的权值即可。
统计点数，任意选择一个起点作为DFS树的根，进行DFS，并递归统计当前点的子树的点数，这是一边的点，剩余的点即为另一边的点。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=100010;
typedef long long LL;
struct edgeType
{int u,v,w;edgeType(){}edgeType(int u,int v,int w):u(u),v(v),w(w){}
};
vector<edgeType> edge;//存储所有的边
struct adj
{int v,w;adj(){}adj(int v,int w):v(v),w(w){}
};
vector<adj> Edge[MAXN];//邻接表
int n,m;
int fa[MAXN];//并查集
int sum[MAXN];//统计某个点所有的子数包含的点数
double dis;bool cmp(const edgeType &a,const edgeType &b)
{return a.w<b.w;
}
int Find(int x)
{if(fa[x]==x) return x;return fa[x]=Find(fa[x]);
}
LL kruskal()
{sort(edge.begin(),edge.end(),cmp);for(int i=1;i<=n;i++){fa[i]=i;}LL ans=0;for(int i=0;i<(int)edge.size();i++){int u=edge[i].u;int v=edge[i].v;int w=edge[i].w;int fu=Find(u);int fv=Find(v);if(fu==fv) continue;fa[fu]=fv;ans=ans+(LL)w;Edge[u].push_back(adj(v,w));Edge[v].push_back(adj(u,w));}return ans;
}void dfs(int root,int father)
{sum[root]=1;for(int i=0;i<(int)Edge[root].size();i++){int son=Edge[root][i].v;int len=Edge[root][i].w;if(son==father) continue;dfs(son,root);sum[root]+=sum[son];dis=dis+(double)(n-sum[son])*(double)sum[son]*(double)len;}
}int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);edge.clear();for(int i=1;i<=n;i++)Edge[i].clear();memset(sum,0,sizeof(sum));dis=0.0;for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);edge.push_back(edgeType(u,v,w));}LL ans=kruskal();dfs(1,0);cout<<ans<<" ";double total=1.0*n*(n-1)/2;printf("%.2lf\n",dis/total);}return 0;
}这篇关于2016 Multi-University Training Contest 1-1001---HDU 5723 Abandoned country(DFS+最小生成树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
