P3381 【模板】最小费用最大流

hello everyone，大家好，我是love——putter，好久没发题解了（因为没素材了）所以，今天来发一下P3381 【模板】最小费用最大流的题解

题目描述

给出一个包含 nn 个点和 mm 条边的有向图（下面称其为网络） G=(V,E)G=(V,E)，该网络上所有点分别编号为 1 \sim n1∼n，所有边分别编号为 1\sim m1∼m，其中该网络的源点为 ss，汇点为 tt，网络上的每条边 (u,v)(u,v) 都有一个流量限制 w(u,v)w(u,v) 和单位流量的费用 c(u,v)c(u,v)。

你需要给每条边 (u,v)(u,v) 确定一个流量 f(u,v)f(u,v)，要求：

1. 0 \leq f(u,v) \leq w(u,v)0≤f(u,v)≤w(u,v)（每条边的流量不超过其流量限制）；
2. \forall p \in \{V \setminus \{s,t\}\}∀p∈{V∖{s,t}}，\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)∑(i,p)∈E​f(i,p)=∑(p,i)∈E​f(p,i)（除了源点和汇点外，其他各点流入的流量和流出的流量相等）；
3. \sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)∑(s,i)∈E​f(s,i)=∑(i,t)∈E​f(i,t)（源点流出的流量等于汇点流入的流量）。

定义网络 GG 的流量 F(G)=\sum_{(s,i)\in E}f(s,i)F(G)=∑(s,i)∈E​f(s,i)，网络 GG 的费用 C(G)=\sum_{(i,j)\in