Bonus 奖励计划

Bonus 奖励计划

Time Limit:3000MS Memory Limit:65536K
Total Submit:58 Accepted:16
Case Time Limit:1000MS

Description


Input

请做到文件底结束,对于每一组:
第一行包含一个正整数N,表示城市的数目。
接下来的N-1行,每行包含2个整数,Ai、Bi,表示Ai和Bi间有一条双向的旅行通道。

Output

对于每一组测试数据,输出一行:
为一个实数,表示平均的支付费用,保留(四舍五入)至小数点后6位。

Sample Input

Sample Output

Hint

10%的数据中N ≤ 10;
30%的数据中N ≤ 100;
50%的数据中N ≤ 1000。
100%的数据中2 ≤ N ≤ 10000,T ≤ 10,1 ≤ Ai,Bi ≤ N,Ai≠Bi。
数据保证任意两个城市之间有且只有一条路径(Path)。

Source

北京2010
额。。看上去很难实际上还是挺水滴。。关键是给每条边的边权赋值成这个点被穿过的概率。。那么答案就是所有路径长度的平均值。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
const int inf=~0U>>1,maxn=10000;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>::iterator it;
vector<int> E[maxn];
int n,Size[maxn];
double Ans,Sum[maxn];
void Clear()
{
    rep(i,maxn)E[i].clear();
}

void AddEdge(int s,int t)
{
    E[s].pb(t);E[t].pb(s);
}

bool Init()
{
    Clear();
    if(scanf("%d",&n)!=1)return false;

    int s,t;
    rep(i,n-1)
    {
        scanf("%d%d",&s,&t);
        –s;–t;
        AddEdge(s,t);
    }

    return true;
}
void Dfs(int x,int f)
{
    Size[x]=1;Sum[x]=0;
    tr(e,E[x])if(*e!=f)
    {
        Dfs(*e,x);
        Size[x]+=Size[*e];
    }
    tr(e,E[x])if(*e!=f)
    {
        double c=double(Size[*e])*(n-Size[*e])/(n*(n-1)/2);
        //cout<<(*e)<<"<->"<<x<<":"<<c<<endl;
        Sum[x]+=Size[*e]*c+Sum[*e];
        Ans+=(Size[x]-Size[*e])*(Sum[*e]+c*Size[*e]);
    }
}

void Solve()
{
    Ans=0;
    Dfs(0,-1);
    printf("%0.6lfn",Ans/((n-1)*n/2));
}
int main()
{
    //freopen("in","r",stdin);
    while(Init())Solve();
}

1.0000000.8888890.7500000.84000021 231 22 341 21 31 451 25 22 34 3

2 thoughts on “Bonus 奖励计划

  1. 回复ad饕饕不绝:囧。。我脑缺了。。其实只要把c的平方全部加起来就可以了。。说白了就是每条边同时出现在两条路径中的概率,就是出现在一条中的平方。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>