hdu_5723_Abandoned country(最小生成树)

题意：

让你求最小生成树的花费，然后求任给两点的期望路程

题解：

最小生成树大家都会求，Kruskal这里要改改，因为后面要求任意两点的期望路程，我们这里Kruskal 记录下最小生成树的边，然后通过DFS把树建出来，最后找每条边经过了多少次，然后乘上对应的组合，比如样列，第一条边权为1的边，这条边左边只有一个节点，右边有3个节点，那么这条边就会经过3次，所以这条边的贡献就是1(左边点个数)*3(右边点个数)*1(边权)，依次类推，然后最后总和除以(n*(n-1)/2)，因为任意点对有这么多种组合的方式，这里的数据居然没有设计成最后除会爆double的，所以不用边除边加，当然保险的是边除边加

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define F(i,a,b) for(int i=a;i<=b;i++)
 4 using namespace std;
 5 
 6 const int N=1e5+7,M=1e6+7;
 7 int n,m,g[N],nxt[N*2],v[N*2],ed,f[N],a[N],sz[N];
 8 
 9 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
10 
11 struct edge{
12     int u,v,w;
13     bool operator<(const edge &b)const{return w<b.w;}
14 }e[M];
15 
16 inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
17 
18 void Kruskal(int tot=0){
19     sort(e+1,e+1+m);
20     F(i,1,n)f[i]=i;
21     F(i,1,m){
22         int fu=find(e[i].u),fv=find(e[i].v);
23         if(fu!=fv)a[++tot]=i,f[fu]=fv;
24         if(tot==n-1)break;
25     }
26 }
27 
28 void dfs(int x,int pre){
29     sz[x]=1;
30     for(int i=g[x];i;i=nxt[i])
31         if(v[i]!=pre)dfs(v[i],x),sz[x]+=sz[v[i]];
32 }
33 
34 int main(){
35     int t;
36     scanf("%d",&t);
37     while(t--){
38         scanf("%d%d",&n,&m);
39         F(i,1,m)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
40         Kruskal();
41         F(i,1,n)g[i]=0;ed=0;
42         F(i,1,n-1){
43             adg(e[a[i]].u,e[a[i]].v);
44             adg(e[a[i]].v,e[a[i]].u);
45         }
46         dfs(1,1);
47         double ans=0,div=(1.0*n*(n-1)/2);
48         long long an=0;
49         F(i,1,n-1){
50             int u=e[a[i]].u,v=e[a[i]].v;
51             if(sz[u]<sz[v])u^=v,v^=u,u^=v;
52             an+=e[a[i]].w;
53             ans+=(double)(sz[v])*(n-sz[v])*e[a[i]].w;
54         }
55         printf("%lld %.2lf
",an,ans/div);
56     }
57     return 0;
58 }

View Code