网络最大流

题目描述

给出一个网络图，以及其源点和汇点，求出从源点到汇点经过各边能使用的网络最大流。

输入

第一行包含四个正整数 n,m,s,t，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 m 行每行包含三个正整数 u_i,v_i,w_i，表示第 i 条有向边从 u_i 出发，到达 v_i，边权为 w_i（即该边最大流量为 w_i）。

输出

一行，包含一个正整数，即为该网络的最大流。

样例

提示

样例输入输出 1 解释

题目中存在 3 条路径：

• 4\to 2\to 3，该路线可通过 20 的流量。
  
• 4\to 3，可通过 20 的流量。
  
• 4\to 2\to 1\to 3，可通过 10 的流量（边 4\to 2 之前已经耗费了 20 的流量）。
  
  故流量总计 20+20+10=50。输出 50。
  

数据规模与约定

• 对于 30\% 的数据，保证 n\leq10，m\leq25。
  
• 对于 100\% 的数据，保证 1 \leq n\leq200，1 \leq m\leq 5000，0 \leq w\lt 2^{31}。
  

来源

模板