Skip to content

Files

Latest commit

5f6757e · Oct 30, 2021

History

History

2234

README.md

题目

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

其中有 S c 个源点,$T_c$ 个汇点。

图中可能存在重边和自环。

求整个网络的最大流。

输入格式

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

第二行包含 S c 个整数,表示所有源点的编号。

第三行包含 T c 个整数,表示所有汇点的编号。

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

点的编号从 1 n

输出格式

输出一个整数表示整个网络的最大流。

数据范围

2 n 10000 ,

1 m 10 5 ,

0 c 10000 ,

保证源点集合和汇点集合没有交集。

输入样例:

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

输出样例:

70

题解