| 题目名称 | 938. [河南省队2012] 阻击补给线 |
|---|---|
| 输入输出 | t2bb.in/out |
| 难度等级 | ★ |
| 时间限制 | 200 ms (0.2 s) |
| 内存限制 | 32 MiB |
| 测试数据 | 10 |
| 题目来源 |
 kaaala
于2012-07-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：15， 通过率：6.67% | ||||
 kaaala |
100 | 0.389 s | 1.30 MiB | C++ |
 wo shi 刘畅 |
90 | 0.081 s | 3.99 MiB | Pascal |
 了反取字名我擦 |
90 | 0.083 s | 1.15 MiB | C++ |
 Makazeu |
90 | 0.092 s | 1.46 MiB | C++ |
|
Makazeu |
60 | 0.090 s | 1.46 MiB | C++ |
 鷐栩 |
30 | 0.052 s | 3.15 MiB | C++ |
 H J H |
30 | 0.207 s | 3.98 MiB | Pascal |
 真呆菌 |
30 | 0.378 s | 23.24 MiB | C++ |
 RP++ |
30 | 1.153 s | 7.04 MiB | C++ |
|
RP++ |
30 | 1.275 s | 0.58 MiB | C++ |
| 本题关联比赛 | |||
| 20120720 | |||
| 关于 阻击补给线 的近10条评论(全部评论) |
|---|
【题目描述】
后勤补给对与一个处于战争状态的军团是极其重要的。你作为军团掠夺联队的一员，你的指挥管命令你们去切断敌对军团的后勤补给线路。要想切断敌人的一条交通通道至少需要装载量为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