Problem
题目蓝链
推荐不要看原题面，原题题面已经过转化
一颗n个点的带边权且以一号点为根的有根树，边权为走这条边所要花的时间
树上有一个宝箱位于一号点以外的点，但是不知道宝箱具体在那个点
如果有一个人从一号点出发，每条边只能走不超过2次，按照最优策略走，问找到宝藏的期望时间。
\(n \leq10^5,边权\leq1000\)
Solution
一开始看到这道题，完全不知道要干什么
那就只能转化题目
令\(t_i\)表示第一次到达\(i\)点的时间
题目要求的期望就变成了
\[ \frac{\sum_{i = 1}^{i \leq n}t_i}{(n - 1)} \]
然后我们就可以贪心了
定义点\(x\)的点权\(val_x\)为遍历\(x\)为根的子树所需要的时间与子节点个数的比值。
所以对于每个节点\(x\)的儿子,我们按照\(val\)从小到大排序后再按顺序遍历就可以了
Code
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
inline int read(){
int res = 0, fl = 1;
char r = getchar();
for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 2e5 + 10;
vector<pii>g[Maxn];
long double val[Maxn];
int siz[Maxn];
void dfs(int now, int pa){
siz[now] = 1;
for (int i = g[now].size() - 1; i >= 0; --i){
int nxt = g[now][i].fst;
if(pa == nxt) continue;
//val[now] += g[now][i].snd;
val[nxt] += g[now][i].snd;
dfs(nxt, now);
val[now] += val[nxt];
siz[now] += siz[nxt];
}
}
LL Time, t[Maxn];
bool cmp(pii A, pii B){
return val[A.fst] > val[B.fst];
}
void Dfs(int now, int pa){
for (int i = g[now].size() - 1; i >= 0; --i){
int nxt = g[now][i].fst;
if(nxt == pa) continue;
val[nxt] = 1.00 * val[nxt] / siz[nxt];
}
sort(g[now].begin(), g[now].end(), cmp);
t[now] = Time;
for (int i = g[now].size() - 1; i >= 0; --i){
int nxt = g[now][i].fst;
if(pa == nxt) continue;
Time += g[now][i].snd;
Dfs(nxt, now);
Time += g[now][i].snd;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
int n = read();
for (int i = 1; i < n; ++i){
int x = read(), y = read(), z = read();
g[x].push_back(mp(y,z));
g[y].push_back(mp(x,z));
}
dfs(1, 0);
Dfs(1, 0);
long double ans = 0;
for (int i = 1; i <= n; ++i) ans += t[i];
printf("%.6Lf\n",1.00 * ans / (n - 1));
return 0;
}
转载于:https://www.cnblogs.com/LZYcaiji/p/10616540.html
相关资源：JAVA上百实例源码以及开源项目
