问题描述
给定一颗 n 个点的树，树边带权，试求一个排列 P，使下式的值最大
[sum_{i=1}^{n-1}maxflow(P_i,P_{i+1})
]
其中 maxflow(s, t) 表示从点 s 到点 t 之间的最大流，即从 s 到 t 的路径上最小的边权。
输入格式
第一行一个整数 n，表示点数
下接 n 1 行，每行三个数 u, v, w 表示一条连接点 u 和点 v 权值为 w 的边
输出格式
输出一行一个整数，表示答案
样例输入
2
1 2 2333
样例输出
2333
数据范围
对于前 5% 的数据满足 n ≤8
对于前 40% 的数据满足 n ≤200
对于前 60% 的数据满足 n ≤2000
对于 100% 的数据满足 n≤100000
解析
考虑如何才能使题中所给的式子最小。我们从小往大加边，自然我们想要使小的边出现的越少越好，所以假设这条边为(u,v)，最后的排列一定长这样：
[P_1,P_2,P_3,...P_{k},u,v,P_{k+3},P_{k+4},...,P_n
]
即该边两侧的点在排列中分别处于两个端点的两边。由此，最后我们一定能做到每条边只记一次贡献。最后的答案即为所有边权之和。
代码
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n,i,ans;
signed main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n;
for(i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
ans+=w;
}
cout<<ans<<endl;
return 0;
}