HDU 5723 Abandoned country mst+樹上期望

題意：

求最小生成樹然後求樹上任意兩點距離的期望

用kruskal求最小生成樹的時候建樹然後再樹上dfs求的總距離然後除以比對數

ACcode：

#pragma warning(disable:4786)//使命名長度不受限制
#pragma comment(linker, "/STACK:102400000,102400000")//手工開棧
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d,&x,&y,&z)
#define rdl(x) scanf("%I64d,&x);
#define rds(x) scanf("%s",x)
#define rdc(x) scanf("%c",&x)
#define ll long long int
#define ull unsigned long long
#define maxn 1000005
#define mod 1000000007
#define INF 0x3f3f3f3f //int 最大值
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define MT(x,i) memset(x,i,sizeof(x))
#define PI  acos(-1.0)
#define E  exp(1)
#define eps 1e-8
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll mul(ll a,ll b,ll p){ll sum=0;for(;b;a=(a+a)%p,b>>=1)if(b&1)sum=(sum+a)%p;return sum;}
inline void Scan(int &x) {
      char c;while((c=getchar())<'0' || c>'9');x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}
using namespace std;
int f[maxn];
struct Edge{
    int u,v,w;
}my[maxn];
vector<pair<int,int> >edge[maxn];
int tot;
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
inline void add(int u,int v,int w){
    my[tot].u=u;my[tot].v=v;my[tot++].w=w;
}
int find_(int x){
    if(f[x]==-1)return x;
    return f[x]=find_(f[x]);
}
int n,loop,m;
ll kruskal(ll n){
    memset(f,-1,sizeof(f));
    sort(my,my+tot,cmp);
    ll cnt=0,ans=0;
    for(int i=0;i<tot;++i){
        int t1=find_(my[i].u);
        int t2=find_(my[i].v);
        if(t1!=t2){
            ans+=my[i].w;
            f[t1]=t2;
            edge[my[i].u].push_back(make_pair(my[i].v,my[i].w));
            edge[my[i].v].push_back(make_pair(my[i].u,my[i].w));
            cnt++;
        }
        if(cnt==n-1)break;
    }
    if(cnt<n-1)return -1;
    else return ans;
}
ll len;
int dfs(int x,int f){
    int ans=0;
    for(int i=0;i<edge[x].size();++i){
        int v=edge[x][i].first;
        if(v==f)continue;
        int tmp=dfs(v,x);
        ans+=tmp;
        len=len+1.0*tmp*(n-tmp)*edge[x][i].second;
    }
    return ans+1;
}
int main(){
    scanf("%d",&loop);
    while(loop--){
        for(int i=0;i<maxn;++i)edge[i].clear();
        scanf("%d%d",&n,&m);
        tot=0;
        for(int i=0;i<m;++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        len=0;
        ll ans=kruskal(n);
        dfs(1,0);
        printf("%I64d %.2lf\n",ans,len*2.0/(1.0*n)/(n-1.0));
    }
    return 0;
}