11392: 【原1392】BJ_drunbier
题目
题目描述
author: 徐世超 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1392
Description
哔酱找到了一份酱星人居住地的地图,上面标注着A酱,B酱,C酱,辣酱,甜面酱,蛋黄酱,果酱,上酱,螺旋酱,沙茶酱,等等等等等等酱(好像混进去了很多奇怪的东西)的居住地,它们都散布在乡村田园中。
这N个居住地由乡间小路连成了一棵树。
哔酱在田园间彳(chi)亍(chu)着, 这样迟迟的日影, 这样温暖的寂静, 这片午饮的香味, 对他是多么熟稔。
这带露台,这扇窗, 后面有幸福在窥望, 还有几架书,两张床, 一瓶花......这已是天堂。
这条路他曾经走了多少回! 多少回?......过去都压缩成一堆, 叫人不能分辨,日子是那么相类, 同样幸福的日子,这些孪生姊妹!
是不是今天出门时忘记说“再见”? 是不是早已忘记了田间那芬芳的油菜花香 忘记了交横的乡间小路 于是,他开始沉思: 对所有这乡间小路上的点对(a,b)组成的路径,平均的路径长度是多少?
Input Format
第一行,一个正整数N。
接下来N行,第i行一个数mi,代表节点i的父节点是mi;第二个数li,代表mi到i的边权为li。
特别的,如果i=0代表无父节点。
Output Format
一行一个数,是平均路径长度,保留两位小数。
Sample Input
4
2 1
0 0
2 1
2 1
Sample Output
1.50
数据范围与约定
N≤10000。一个节点的父节点不会是自己。
FineArtz's solution
/* BJ_drunbier */
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
class Node{
public:
vector<int> edge;
int sub = 1;
};
class Edge{
public:
int u = 0, v = 0, len = 0;
};
Node a[10005];
Edge e[10005];
int calcSub(int root){
for (auto i : a[root].edge){
a[root].sub += calcSub(i);
}
return a[root].sub;
}
int main(){
int n, f, w, root, cnte = 0;
cin >> n;
if (n == 1){
cout << "0.00" << endl;
return 0;
}
for (int i = 1; i <= n; ++i){
cin >> f >> w;
if (f == 0){
root = i;
}
else{
a[f].edge.push_back(i);
++cnte;
e[cnte].u = f;
e[cnte].v = i;
e[cnte].len = w;
}
}
calcSub(root);
//for (int i = 1; i <= n; ++i)
// cout << i << ' ' << a[i].sub << endl;
double ans = 0, tmp;
for (int i = 1; i <= cnte; ++i){
tmp = n - a[e[i].v].sub;
tmp = tmp * a[e[i].v].sub;
tmp = tmp * e[i].len;
ans = ans + tmp;
}
ans = ans / n / (n - 1) * 2;
cout << setiosflags(ios::fixed) << setprecision(2) << ans << endl;
return 0;
}
WashSwang's solution
#include <iostream>
using namespace std;
double sum;
long long l[10001];
int num,n,nxt[10001],last[10001],to[10001],root,f,v;
void add(int x,int y,int v){
num++;
nxt[num]=last[x];
last[x]=num;
to[num]=y;
l[num]=v;
}
int dfs(int x){
int son=1,tmp;
for (int i=last[x];i!=0;i=nxt[i]){
tmp=dfs(to[i]);
son+=tmp;
sum+=(n-tmp)*tmp*l[i];
}
return son;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%d%d",&f,&v);
if (f==0) root=i;
else add(f,i,v);
}
dfs(root);
printf("%.2f",sum/(n*(n-1)/2));
return 0;
}