#O1048. 最大流

最大流

题目描述

给定 nn 个点、mm 条有向边的网络,边 (u,v)(u,v) 的容量为 cc,求从源点 ss 到汇点 tt 的最大流。

题目类型

网络流、Dinic

输入格式

第一行四个整数 n,m,s,tn, m, s, t。

接下来 mm 行,每行三个整数 u,v,cu, v, c。

输出格式

一行一个整数,表示最大流。

样例 #1

样例输入 #1

4 5 1 4
1 2 10
1 3 10
2 3 1
2 4 10
3 4 10

样例输出 #1

20

数据规模与约定

数据范围 说明
2≤n≤10002 \le n \le 1000 点数
1≤m≤2×1041 \le m \le 2 \times 10^4 边数
1≤c≤1091 \le c \le 10^9 容量
  • 需用 Dinic 或 ISAP,答案用 long long。