U409708 多源汇最大流

题目描述

给定一个包含 $ 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 \le n \le 10000 $, $ 1 \le m \le 10^5 $, $ 0 \le c \le 10000 $, 保证源点集合和汇点集合没有交集。