来源和评测点
USACO 1993
Poj1273
Syzoj11772
Hdu1532
Caioj1115
题目
「题目大意」
有N条水渠,及M个池塘
给出M条水渠所连接的池塘和所能流过的水量(有向)
求水渠1到水渠M中所能流过的水的最大容量
(Caioj上先池塘后水渠)
(Hdu上多组数据)
「输入格式」
第1行:2个整数N(0<=N<=200)和M(2<=M<=200)
接下来M行: 每行有三个整数:x,y,c
表示一条从点x到点y的有向边,流量为c(0<=c<=10,000,000)
「输出格式」
输出一个整数,即最大流量。
「输入样例1」
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
「输出样例1」
50
理论上可以卡最短路的数据
「输入样例2」
4 4
1 2 10
2 4 5
2 3 20
3 4 10
「输出样例2」
10
分析
网络流教程和题目分类参见:
「OI之路」03图论算法-4网络流
其他网络流题目参见:Tag-网络流
模板题
代码
我的代码n是点数