#M002. [模板题]最大流

    ID: 5629 传统题 2000ms 512MiB 尝试: 44 已通过: 14 难度: 5 上传者: 标签>CF1700提高最大流Dinic残量网络当前弧优化最大流最小割定理

[模板题]最大流

Problem Description

This is a template problem.

Given nn vertices and mm directed edges, each with a specified capacity, determine the maximum flow from vertex ss to vertex tt.

Input Format

The first line contains four integers nn, mm, ss, and tt.
The following mm lines each contain three integers uu, vv, and cc, representing a directed edge from vertex uu to vertex vv with a capacity cc.

Output Format

Output the maximum flow from vertex ss to vertex tt.

Example Input

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

Example Output

14

Constraints and Hints

  • 1⩽n⩽1001 \leqslant n \leqslant 100
  • 1⩽m⩽50001 \leqslant m \leqslant 5000
  • 0⩽c⩽231−10 \leqslant c \leqslant 2^{31} - 1