Abandoned country

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2969 Accepted Submission(s): 725

Problem Description

An abandoned country has

Input

The first line contains an integer

Output

output the minimum cost and minimum Expectations with two decimal places. They separated by a space.

Sample Input

1 4 6 1 2 1 2 3 2 3 4 3 4 1 4 1 3 5 2 4 6

Sample Output

6 3.33

Author

HIT

Source

2016 Multi-University Training Contest 1

题意：

给出n个点和m条边，每条边的权值都不相同，求使得n个点连通而边的权值之和最小，以及随机选2个点作为起点和终点的路径长度的期望

题解：

最小权值直接求最小生成树就好

m条边权值各不相同，所以每个权值对应一个期望，求出最小生成树的时候，期望也一定是最小的

期望是等于每条边的贡献之和除以总路径。

每条边两边的点连通都要经过这条边，所以这条边的贡献就是s（其中一边的点的数）*（n-s）*w（权值）；

求每条边的一边的点，可以利用dfs

源代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,m;
struct node
{
    int x,y,w;
    node(int xx,int yy,int ww):x(xx),y(yy),w(ww) {}
};
vector<node> a;
struct Node
{
    int y,w;
    Node(int yy,int ww):y(yy),w(ww) {}
};
vector<Node> b[maxn];
int f[maxn];
bool cmp(const node &i,const node &j)
{
    return i.w<j.w;
}
int finds(int x)
{return f[x] == x?x:f[x] = finds(f[x]);}
long long Kruskal()
{
    long long ans=0;
    for(int i=1; i<=n; i++) f[i]=i;
    sort(a.begin(),a.end(),cmp);
    for(int i=0; i<a.size(); i++)
    {
        int x=finds(a[i].x);
        int y=finds(a[i].y);
        if(x==y)continue;
        f[x]=y;
        ans+=a[i].w;
        b[a[i].x].push_back(Node(a[i].y,a[i].w));
        b[a[i].y].push_back(Node(a[i].x,a[i].w));
    }
    return ans;
}
int s[maxn];
double d[maxn];
void dfs(int root,int father)
{
    s[root]=1;
    for(int i=0; i<b[root].size(); i++)
    {
        int son=b[root][i].y;
        int l=b[root][i].w;
        if(son==father) continue;
        dfs(son,root);
        s[root]+=s[son];
        d[root]+=d[son]+((double)s[son]*(n-s[son]))*l;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        a.clear();
        for(int i=0; i<m; i++)
        {
            int x,y,w;
            scanf("%d%d%d",&x,&y,&w);
            a.push_back(node(x,y,w));
        }
        memset(s,0,sizeof(s));
        memset(d,0,sizeof(d));
        for(int i=1; i<=n; i++)
            b[i].clear();
        long long ans=Kruskal();
        dfs(1,0);
        long long g=(long long)n*(n-1)/2;
        printf("%I64d %.2lf
",ans,d[1]/(double)g);
    }
    return 0;
}