1. 首页
2. DFS, 生成树
3. 本页

HDU 5723 Abandoned country (最小生成树+dfs)

题目链接：点我~~

题意：~~

思路：首先注意到任意两条边的边权是不一样的，由此得知最小生成树是唯一的，最小生成树既然 是唯一的，那么期望其实也就是唯一的，不存在什么最小期望。求完最小生成树之后，接下 来的问题就可以转换成在最小生成树上求任意两点之间距离的平均值，对于每条边，统计所 有的路径用到此边的次数，也就是边的两端的点数之积。那么这条边的总贡献就是次数*边 权。最后得到所有边的贡献之和再除以总路径数$n\ast (n-1)/2$就是答案。可以O(n)求出。任取一点为根dfs，对每个点$i$记录其子树包含的点数（包括其自身），设点数为sum[i]，则$i$的父亲一侧的点数即为n-sum[i]。一边遍历一边统计就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define mp make_pair
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN=100000+10;
const int MAXM=1000000+10;

vector<PI > G[MAXN];
int F[MAXN];
struct Edge
{
    int u,v,w;
} edge[MAXM*2];
int tol;

void addedge(int u,int v,int w)
{
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(F[x]==-1)return x;
    else return F[x]=find(F[x]);
}
LL Kruskal(int n)
{
    memset(F,-1,sizeof(F));
    sort(edge,edge+tol,cmp);
    int cnt=0;
    LL ans=0;
    for(int i=0; i<tol; i++)
    {
        int u=edge[i].u;
        int v=edge[i].v;
        int w=edge[i].w;
        int t1=find(u);
        int t2=find(v);
        if(t1!=t2)
        {
            G[u].push_back(mp(v,w));
            G[v].push_back(mp(u,w));
            ans+=w;
            F[t1]=t2;
            cnt++;
        }
        if(cnt==n-1)break;
    }
    if(cnt<n-1)return -1;
    else return ans;
}

double res;
int n;

int dfs(int x,int fa)
{
    int ans=0;
    for(int i=0; i<G[x].size(); ++i)
    {
        if(G[x][i].first==fa)
            continue;
        int tmp=dfs(G[x][i].first,x);
        ans+=tmp;
        res+=1.0*tmp*(n-tmp)*G[x][i].second;
    }
    return ans+1;
}


int main()
{
    int t;
    scanf("%d",&t);
    int m;
    int u,v,w;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)
        {
            G[i].clear();
        }
        tol=0;
        for(int i=0; i<m; ++i)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        //cout<<Kruskal(n);
        printf("%lld",Kruskal(n));
        res=0;
        dfs(1,0);
        printf(" %.2lf\n",2.0*res/(n*1.0*(n-1)));

    }

    return 0;
}