| 比赛场次 | 156 |
|---|---|
| 比赛名称 | 20120720 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-07-20 08:00:00 |
| 结束时间 | 2012-07-20 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 群众喜闻乐见的有关于游戏的题目 |
| 题目名称 | 阻击补给线 |
|---|---|
| 输入输出 | t2bb.in/out |
| 时间限制 | 200 ms (0.2 s) |
| 内存限制 | 32 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 wo shi 刘畅 |
AAWAAAAAAA | 0.064 s | 3.99 MiB | 90 |
 了反取字名我擦 |
AAWAAAAAAA | 0.065 s | 1.15 MiB | 90 |
 临轩听雨ゐ |
AAWWAWWWWW | 0.070 s | 0.31 MiB | 30 |
 Citron酱 |
AAWWAWWWWW | 0.087 s | 0.29 MiB | 30 |
 Makazeu |
AAWWAWWWWW | 0.095 s | 0.32 MiB | 30 |
 苏轼 |
AAWWAWWWWW | 0.165 s | 0.32 MiB | 30 |
 Truth.Cirno |
AAWWAWWWWW | 0.228 s | 1.72 MiB | 30 |
 11111111 |
AAWWWWWWWW | 0.079 s | 0.31 MiB | 20 |
【题目描述】
后勤补给对与一个处于战争状态的军团是极其重要的。你作为军团掠夺联队的一员，你的指挥管命令你们去切断敌对军团的后勤补给线路。要想切断敌人的一条交通通道至少需要装载量为w的掠夺小队（假设小队的每个成员的装载量为1）去驻守那里。只要敌人缺少任何一座补给站都将无法进行补给。掠夺联队的兵力并不足以遍布整个宇宙，因此你的指挥官要求你求出如何以最少的兵力切断敌人的后勤补给线路。
【输入格式】
第一行为两个整数N、M (2 ≤ N ≤ 500, 0 ≤ M ≤ N × (N − 1) ⁄ 2) 表示有N个安全点，和M条交通通道
第i+1至第i+m行，每行三个整数si,ti,wi（0<=s,t
【输出格式】
一个整数X表示至少需要多少个军团成员去切断敌人的补给线路
如果补给线路本身就不需要兵力输出0
【样例输入】
t2bb.in
3 3
0 1 1
1 2 1
2 0 1
【样例输出】
t2bb.out
2