一开始考虑所有边都是单独的一条路径

然后尽量多的合并

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream> using namespace std; void setIO(const string& s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<typename Q> Q read(Q& x) {
static char c, f;
for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;
for(x = ; isdigit(c); c = getchar()) x = x * + c - '';
if(f) x = -x;
return x;
}
template<typename Q> Q read() {
static Q x; read(x); return x;
} const int N = + ;
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif static int du[N], mx[N];
int T = read<int>();
for(int cas = ; cas <= T; cas++) {
memset(du, , sizeof du);
memset(mx, , sizeof mx);
int ans = ;
int u, v, w, n = read<int>();
for(int i = ; i < n; i++) {
read(u), read(v), read(w);
du[u] += w, du[v] += w;
mx[u] = max(mx[u], w);
mx[v] = max(mx[v], w);
ans += w;
} for(int u = ; u <= n; u++) {
if((mx[u] << ) <= du[u]) ans -= du[u] >> ;
else ans -= du[u] - mx[u];
} printf("Case #%d: %d\n", cas, ans);
} return ;
}

最新文章

  1. 背水一战 Windows 10 (9) - 资源: 资源限定符概述, 资源限定符示例
  2. iOS - 二维码扫描和应用跳转
  3. java设计模式--工厂模式
  4. You are note Hk
  5. 微信公众平台项目中遇到的小问题40016,Invalid button size
  6. 在Android Studio 中正确使用adil ”绝对经典“
  7. C# 必应代码搜索
  8. line-height属性使文字垂直居中原理
  9. 多校6 1003 HDU5795 A Simple Nim (sg函数)
  10. matlab读取多幅图片,并对读取的图片降采样和双三次插值
  11. Kotlin Vertx
  12. CCIE路由实验(5) -- BGP负载均衡
  13. ng-file-upload(在单文件选择,并且通过点击“上传”按钮上传文件的情况下,如何在真正选择文件之前保留上一文件信息?)
  14. javaweb-番外篇-Commons-FileUpload组件上传文件
  15. 关于css选择器中有小数点的标签获取
  16. GeoServer中sld文件的获取来源
  17. Photoshop打造唯美的蓝色古装外景人物图片
  18. 持续集成CI相关的几个概念
  19. TIMESTAMPDIFF用法
  20. SVG前戏—让你的View多姿多彩

热门文章

  1. ubuntu14.04.1 LTS 64bits较快的更新源
  2. css 文本两端对齐
  3. SQL Server2012连接SQL Server2000完美解决方案
  4. excel快递单号查询工具以及源码
  5. Android多点触摸 与 手势识别
  6. .Net C/S系统开发框架(楚楚原创)
  7. X-window
  8. SignalR介绍与Asp.net,前台即时通信【转】
  9. 写个自动下载安装Ant的shell脚本【一】
  10. LeetCode解题报告:Linked List Cycle &amp;&amp; Linked List Cycle II