【模板】网络最大流

题目描述

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

输入输出格式

输入格式:

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)

输出格式:

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

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=25

对于70%的数据:N<=200,M<=1000

对于100%的数据:N<=10000,M<=100000

样例说明:

题目中存在3条路径:

4–>2–>3,该路线可通过20的流量

4–>3,可通过20的流量

4–>2–>1–>3,可通过10的流量(边4–>2之前已经耗费了20的流量)

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


Dinic算法

首先构建层次图(一个点只能沿他深度+1的点走)

然后在层次图中增广


 

发表评论