#P3376. 【模板】网络最大流

【模板】网络最大流

题目描述

如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。

输入格式

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

接下来 mm 行每行包含三个正整数 ui,vi,wiu_i,v_i,w_i,表示第 ii 条有向边从 uiu_i 出发,到达 viv_i,边权为 wiw_i(即该边最大流量为 wiw_i)。

输出格式

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

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
50

提示

样例输入输出 1 解释

题目中存在 33 条路径:

  • 4234\to 2\to 3,该路线可通过 2020 的流量。
  • 434\to 3,可通过 2020 的流量。
  • 42134\to 2\to 1\to 3,可通过 1010 的流量(边 424\to 2 之前已经耗费了 2020 的流量)。

故流量总计 20+20+10=5020+20+10=50。输出 5050


数据规模与约定

  • 对于 30%30\% 的数据,保证 n10n\leq10m25m\leq25
  • 对于 100%100\% 的数据,保证 1n2001 \leq n\leq2001m50001 \leq m\leq 50000w<2310 \leq w\lt 2^{31}