| 题目名称 | 885. 草地排水 |
|---|---|
| 输入输出 | ditch.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 12 |
| 题目来源 |
 sywgz
于2012-07-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：222， 提交：407， 通过率：54.55% | ||||
 qing |
100 | 0.000 s | 0.00 MiB | C++ |
 kxxy |
100 | 0.000 s | 0.00 MiB | C++ |
 AAAAAAAAAA |
100 | 0.000 s | 0.00 MiB | C++ |
 Arrow |
100 | 0.000 s | 0.00 MiB | C++ |
 Cooook |
100 | 0.000 s | 0.00 MiB | C++ |
 Narcissus |
100 | 0.000 s | 0.00 MiB | C++ |
 xyz117 |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_Ivan |
100 | 0.000 s | 0.00 MiB | C++ |
 LadyLex |
100 | 0.000 s | 0.00 MiB | C++ |
|
Narcissus |
100 | 0.000 s | 0.00 MiB | C++ |
| 关于 草地排水 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
艹，de了两个小时bug才发现是加边时a写成b了，结果指向自己……居然还A了8个点
 | ||||
|
| ||||
|
最爱网络流
| ||||
|
练习一下Dinic
 XDDD
2018-01-25 20:11
21楼
| ||||
|
我去。。。样例的点T了什么鬼
 swttc
2017-10-09 11:09
20楼
| ||||
|
这竟然有重边 坑我一把
 LCWhiStLe
2017-08-13 08:52
19楼
| ||||
|
1A dinic板子练手
| ||||
|
一直过不去，数据下下来能过交上去就w
 CSU_Turkey
2017-07-09 07:08
17楼
| ||||
|
| ||||
|
| ||||
Untitled
Hale
Shirry
Hallmeow【题目描述】
在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
【输入格式】
第 $1$ 行：两个用空格分开的整数 $N(0\le N\le 200)$ 和 $M(2\le M\le 200)$。$N$ 是农夫约翰已经挖好的排水沟的数量，$M$ 是排水沟交叉点的数量。交点 $1$ 是水潭，交点 $M$ 是小溪。
第二行到第 $N+1$ 行：每行有三个整数，$S_i$，$E_i$ 和 $C_i$。$S_i$ 和 $E_i$（$1\le S_i,E_i\le M$）指明排水沟两端的交点，雨水从 $S_i$ 流向 $E_i$。$C_i(0\le C_i\le 10,000,000)$ 是这条排水沟的最大容量。
【输出格式】
输出一个整数，即排水的最大流量。
【样例输入】
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10
【样例输出】
50
【来源】
USACO/ditch(译by Felicia Crazy)