比赛 不平凡的世界 评测结果 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;
}