比赛 |
不平凡的世界 |
评测结果 |
AWWWWWEEEE |
题目名称 |
不平凡的引线 |
最终得分 |
10 |
用户昵称 |
Binary10 |
运行时间 |
0.946 s |
代码语言 |
C++ |
内存使用 |
3.03 MiB |
提交时间 |
2015-11-05 10:21:47 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010, maxm = 200010;
int head[maxn], n, m, tot = 0, deg[maxn];
int next[maxn], v[maxn], w[maxn];
int p[maxn], f[maxn], g[maxn], root = -1;
double ans = 0;
void add(int a, int b, int c){
v[++tot] = b; w[tot] = c;
next[tot] = head[a];
head[a] = tot;
deg[a]++; deg[b]++;
}
void dfs(int u, int fa){
for(int i = head[u]; i; i = next[i])
if(v[i] != fa) dfs(v[i], p[v[i]] = u);
}
void dfs2(int u){
if(deg[u] <= 2) f[u] = 0;
if(f[u] != -1) return;
f[u] = INF;
for(int i = head[u]; i; i = next[i])
if(v[i] != p[u]){
dfs2(v[i]);
f[u] = min(f[u], f[v[i]] + w[i]);
}
}
void dfs3(int u){
if(deg[u] <= 2) return;
for(int i = head[u]; i; i = next[i])
if(v[i] != p[u]){
dfs3(v[i]);
int x = f[v[i]], y = f[u];
if(x < y) swap(x, y);
double t = y;
if(x - y > w[i]) t += w[i];
else t += (x - y) + (w[i] - (x - y)) / 2.0;
if(t > ans) ans = t;
}
}
int main()
{
freopen("firelead.in", "r", stdin);
freopen("firelead.out", "w", stdout);
scanf("%d",&m);
n = m + 1;
int a, b, c;
for(int i = 0; i < m; i++){
scanf("%d%d%d", &a, &b, &c);
add(a, b, c); add(b, a, c);
}
for(int i = 1; i <= n; i++)
if(deg[i] > 2){ root = i; break;}
memset(p, -1, sizeof(p));
memset(f, -1, sizeof(f));
dfs(root, -1);
dfs2(root);
dfs3(root);
printf("%.1f\n", ans);
return 0;
}