1. Preface

Cost flow, fully known as minimum cost maximum flow, is a branch of network flow.

The problem of minimum cost and maximum flow is described as follows:

Give a network \ (g = < V, E > \), and each edge has two weights: \ (f,v \).

\(f \) represents the maximum flow of this side, \ (v \) represents the unit cost, that is to say, every unit flow from this side will increase the cost of \ (v \).

Now the minimum cost and maximum flow of this network are required, that is, the total cost is the minimum under the condition of ensuring the maximum total flow.

Before moving on, you need to know something about:

1. SPFA shortest path algorithm. Portal: P3371 [template] single source shortest path (weakened version)
2. EK solves the maximum flow. Portal: Algorithm learning notes: network flow #2 -- EK to solve the maximum flow

2. Detailed explanation

Template questions: P3381 [template] minimum cost maximum flow

First, review the idea of EK to solve the maximum flow:

BFS is used to constantly find Zengguang road. After finding one at a time, the traffic on this side is updated, and the reverse side is established to go back.

But now a restriction is added: the total cost is the minimum except the maximum total flow.

Ah, this? How do you do that?

Suppose there are now two paths from \ (s \) to \ (t \).

Let's discuss it in categories:

• If the two paths can flow through the same flow, we need to find the one with the lower cost, which can use the shortest path to find the augmented path.
• If the two paths can flow through different flows:
  • If the cost of the side with large flow is relatively small, this path will be found when looking for the Zengguang road in the shortest path, so as to ensure the maximum flow and the minimum cost.
  • But if the traffic is large, which side costs more? So the other side was found when running the shortest circuit for the first time, and the correctness seems to be out of guarantee.
  • However, the side with large traffic is not traversed for the first time, so it is an augmented path in the figure. According to the steps of EK to solve the maximum flow, as long as there is an augmented path, the flow will continue to be pushed, and the edge without flow will be ignored. In this way, even if the first time you find an edge with less traffic cost, the edge with more traffic cost will be found later.

To sum up, you only need to use the shortest circuit to replace the BFS in EK to find the minimum cost and maximum flow.

But how to find the shortest path?

A classmate: haven't I studied graph theory? Isn't it just a naked dijkstra?

If your choice is dijkstra, you need to deal with the graph first.

Why? Take a look at the bold part below:

(the screenshot in the editing interface may be a little different from the reading interface)

Reverse side!

In EK, the reverse side is used to repent, that is, give a chance to go back.

If you want to go back, the flow back should reduce a certain amount of cost.

So the cost of the reverse side is the opposite of the cost of the forward side.

So this graph has a negative weight edge.

So dijkstra died

A classmate: ah, no, isn't SPFA easy to get stuck? dijkstra's useless?

In fact, dijkstra can be used after some strange processing of the network, but the problem of general network flow mainly tests the modeling ability, and SPFA will not be too bad.

Of course, I can't help it if I'm really stuck. I'd better write dijkstra honestly.

code:

/*
========= Plozia =========
	Author:Plozia
	Problem:P3381 [[template] minimum cost and maximum flow -- EK writing method
	Date:2021/3/23
========= Plozia =========
*/

#include <bits/stdc++.h>
using std::queue;

typedef long long LL;
const int MAXN = 5e3 + 10, MAXM = 5e4 + 10, INF = 0x7f7f7f7f;
int n, m, s, t, dis[MAXN], Flow[MAXN], Head[MAXN], cnt_Edge = 1, pre[MAXN], ans_flow, ans_spend;
struct EDGE {int to, w, c, Next;} Edge[MAXM << 1];
bool book[MAXN];

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh = (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return (fh == 1) ? sum : -sum;
}
void add_Edge(int u, int v, int w, int c) {Edge[++cnt_Edge] = (EDGE){v, w, c, Head[u]}; Head[u] = cnt_Edge;}
int Min(int fir, int sec) {return (fir < sec) ? fir : sec;}

bool SPFA()
{
	queue <int> q; q.push(s);
	memset(dis, 0x7f, sizeof(dis));
	memset(Flow, 0x7f, sizeof(Flow));
	memset(pre, 0, sizeof(pre));
	memset(book, 0, sizeof(book));
	dis[s] = 0; book[s] = 1;
	while (!q.empty())
	{
		int x = q.front(); q.pop(); book[x] = 0;
		for (int i = Head[x]; i; i = Edge[i].Next)
		{
			int u = Edge[i].to;
			if (Edge[i].w > 0 && dis[u] > dis[x] + Edge[i].c)
			{
				dis[u] = dis[x] + Edge[i].c;
				Flow[u] = Min(Edge[i].w, Flow[x]);
				pre[u] = i;
				if (!book[u]) {book[u] = 1; q.push(u);}
			}
		}
	}
	return dis[t] != INF;
}

void EK()
{
	while (SPFA())
	{
		int x = t;
		for (; x != s; )
		{
			int k = pre[x];
			Edge[k].w -= Flow[t];
			Edge[k ^ 1].w += Flow[t];
			x = Edge[k ^ 1].to;
		}
		ans_flow += Flow[t];
		ans_spend += Flow[t] * dis[t];
	}
}

int main()
{
	n = read(), m = read(), s = read(), t = read();
	for (int i = 1; i <= m; ++i)
	{
		int u = read(), v = read(), w = read(), c = read();
		add_Edge(u, v, w, c); add_Edge(v, u, 0, -c);
	}
	EK(); printf("%d %d\n", ans_flow, ans_spend);
	return 0;
}

3. Summary

EK solves the cost flow by using SPFA instead of BFS.

But according to a certain law: the card EK is legal, and the card dinic is illegal! (I really don't know where this Law comes from), so I also need to master dinic to solve the cost flow.

Portal: Algorithm learning notes: network flow #6 -- dinic solving cost flow