1. 首页
  2. DFS, 生成树

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

题目链接:点我~~

题意:~~

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

 

评分 5.00, 满分 5 星
1
1
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1054 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

2 条评论

gravatar

  1. 小包子 2016-07-24 Google Chrome 52.0.2743.82Windows 10

    没有题意,差评 :smile:

    回复 0楼
  2. 蒂欧娜 2016-07-21 Google Chrome 14.0.802.30Windows 7

    您的博客拥有旺盛的生命力!!

    回复 0楼
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40