#3619. Dinic/ISAP求最大流

Dinic/ISAP求最大流

题目描述

给定一个包含 nn 个点 mm 条边的有向图,并给定每条边的容量,边的容量非负。

图中可能存在重边和自环。求从点 SS 到点 TT 的最大流。

输入格式

第一行包含四个整数 n,m,S,Tn, m, S, T。

接下来 mm 行,每行三个整数 u,v,cu, v, c,表示从点 uu 到点 vv 存在一条有向边,容量为 cc。

点的编号从 11 到 nn。

输出格式

输出点 SS 到点 TT 的最大流。

如果从点 SS 无法到达点 TT 则输出 00。

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7
14

数据规模与约定

对于 100%100\% 的数据:

  • 2≤n≤100002 \le n \le 10000
  • 1≤m≤1000001 \le m \le 100000
  • 0≤c≤100000 \le c \le 10000
  • S≠TS \ne T