曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5489: 最大流

Memory Limit：512 MB Time Limit：5.000 S
Judge Style：Text Compare Creator：
Submit：17 Solved：8
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

给定n个点，m条有向边，给定每条边的容量，求从点s到点t的最大流。

Input

第一行四个整数n,m,s,t 。
接下来的m行，每行三个整数u,v,c，表示起点为u，终点为v，流量为c的一条有向边。

Output

输出点s到点t的最大流。

Sample Input Copy 

10 16 1 2
1 3 2
1 4 2
5 2 2
6 2 2
3 5 1
3 6 1
4 5 1
4 6 1
1 7 2147483647
9 2 2147483647
7 8 2147483647
10 9 2147483647
8 5 2
8 6 2
3 10 2
4 10 2

Sample Output Copy 

8

HINT

1<=n<=1200
1<=m<=120000
1<=c<=231 -1