题目描述
给出一个包含 n nn 个点和 m mm 条边的有向图（下面称其为网络） G = ( V , E ) G=(V,E)G=(V,E)，该网络上所有点分别编号为 1 ∼ n 1 \sim n1∼n，所有边分别编号为 1 ∼ m 1\sim m1∼m，其中该网络的源点为 s ss，汇点为t tt，网络上的每条边 ( u , v ) (u,v)(u,v) 都有一个流量限制 w ( u , v ) w(u,v)w(u,v)和单位流量的费用 c ( u , v ) c(u,v)c(u,v)。
你需要给每条边 ( u , v ) (u,v)(u,v) 确定一个流量 f ( u , v ) f(u,v)f(u,v)，要求：
- 0 ≤ f ( u , v ) ≤ w ( u , v ) 0 \leq f(u,v) \leq w(u,v)0≤f(u,v)≤w(u,v) （每条边的流量不超过其流量限制）；
- ∀ p ∈ { V ∖ { s , t } } \forall p \in \{V \setminus \{s,t\}\}∀p∈{V∖{s,t}}，∑ ( i , p ) ∈ E f ( i , p ) = ∑ ( p , i ) ∈ E f ( p , i ) \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)（除了源点和汇点外，其他各点流入的流量和流出的流量相等）；
- ∑ ( s , i ) ∈ E f ( s , i ) = ∑ ( i , t ) ∈ E f ( i , t ) \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) （源点流出的流量等于汇点流入的流量）。
定义网络 G GG 的流量 F ( G ) = ∑ ( s , i ) ∈ E f ( s , i ) F(G)=\sum_{(s,i)\in E}f(s,i)F(G)=∑
(s,i)∈E
f(s,i)，网络 G GG 的费用 C ( G ) = ∑ ( i , j ) ∈ E f ( i , j ) × c ( i , j ) C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)C(G)=∑
(i,j)∈E
f(i,j)×c(i,j)。
你需要求出该网络的最小费用最大流，即在 F ( G ) F(G)F(G) 最大的前提下，使 C ( G ) C(G)C(G) 最小。
输入格式
输入第一行包含四个整数 n , m , s , t n,m,s,tn,m,s,t，分别代表该网络的点数 n nn，网络的边数 m mm，源点编号 s ss，汇点编号 t tt。
接下来 m mm 行，每行四个整数 u i , v i , w i , c i ，分别代表第 i ii 条边的起点，终点，流量限制，单位流量费用。
输出格式
输出两个整数，分别为该网络的最大流 F ( G ) F(G)F(G)，以及在 F ( G ) F(G)F(G) 最大的前提下，该网络的最小费用 C ( G ) C(G)C(G)。
输入输出样例
4 5 4 3 4 2 30 2 4 3 20 3 2 3 20 1 2 1 30 9 1 3 40 5
50 280
说明/提示
对于 100 % 100\%100% 的数据，1 ≤ n ≤ 5 × 1 0 4 1 \leq n \leq 5\times 10^41≤n≤5×10
4
， 1 ≤ m ≤ 5 × 1 0 4 1 \leq m \leq 5 \times 10^41≤m≤5×10
4
，1 ≤ s 1 \leq s1≤s ,t ≤ n t \leq nt≤n ，0 ≤ w i , c i ≤ 1 0 3 0 \leq w_i,c_i \leq 10^30≤w
i
,c
i
≤10
3
，且该网络的最大流和最小费用 ≤ 2 31 − 1 \leq 2^{31} - 1≤2
31
−1
输入数据随机生成。
思路：
和 EK算法 类似，但每次用B e l l m a n − F o r d Bellman-FordBellman−Ford 算法而非B F S BFSBFS（其实差不多）找增广路。
只要初始流是该流量下的最小费用可行流，每次增广之后的新流都是新流量下的最小费用流。
费用值可正可负
typedef pair<ll, ll> PLL; struct Edge { int u, v, cap, flow, cost; Edge(int _u, int _v, int _cap, int _flow, int _cost) { u = _u, v = _v, cap = _cap, flow = _flow, cost = _cost; } }; struct MinCostMaxFlow { int n, m; vector<Edge> edges; vector<int> G[maxn]; int vis[maxn], dis[maxn], p[maxn], a[maxn]; void init(int x) { this->n = x; for (int i = 0; i <= x; i++) G[i].clear(); edges.clear(); } void add(int u, int v, int cap, int cost) { edges.push_back(Edge(u, v, cap, 0, cost)); edges.push_back(Edge(v, u, 0, 0, -cost)); m = edges.size(); G[u].push_back(m - 2); G[v].push_back(m - 1); } bool BellmanFord(int s, int t, ll &flow, ll &cost) { for (int i = 0; i <= n; i++) dis[i] = 0x3f3f3f3f; memset(vis, 0, sizeof vis); queue<int> que; que.push(s); dis[s] = 0, vis[s] = 0, p[s] = 0, a[s] = 0x3f3f3f3f; while (que.size()) { int u = que.front(); que.pop(); vis[u] = 0; /// not in the queue for (int i = 0; i < G[u].size(); i++) { int id = G[u][i]; Edge e = edges[id]; int to = e.v; if (e.cap > e.flow && dis[to] > dis[u] + e.cost) { dis[to] = dis[u] + e.cost; p[to] = id; a[to] = min(a[u], e.cap - e.flow); if (!vis[to]) { que.push(to); vis[to] = 1; } } } } if (dis[t] >= 0x3f3f3f3f) return false; flow += a[t]; cost += 1LL * dis[t] * 1LL * a[t]; for (int u = t; u != s; u = edges[p[u]].u) { edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } return true; } PLL MinCostAndMaxFlow(int s, int t) { ll flow = 0; ll cost = 0; while (BellmanFord(s, t, flow, cost)); return {flow, cost}; } } solve; int n, m, s, t; int main() { cin >> n >> m >> s >> t; solve.init(n); for (int i = 1; i <= m; i++) { int u = read, v = read, flow = read, cost = read; solve.add(u, v, flow, cost); } PLL ans = solve.MinCostAndMaxFlow(s, t); cout << ans.first << ' ' << ans.second << endl; return 0; }
