洛谷P3381 【模板】最小费用最大流 题解

题目大意

最小费用最大流模板。

解题思路

模板。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 5e4 + 5, M = 5e3 + 5, INF = 1e9;
struct node{
	int to, next, w, c;
}edge[N << 1];
int n, m, S, T;
int head[M], cnt = 0;
int dis[M], in[M];
int cur[M], vis[M];
queue<int> q;

void build(int u, int v, int w, int c) {
	edge[cnt].to = v, edge[cnt].w = w, edge[cnt].c = c;
	edge[cnt].next = head[u], head[u] = cnt++;
}

int spfa() {
	q.push(S);
	in[S] = 1;
	rep(i, 1, n) dis[i] = INF;
	dis[S] = 0;
	while (!q.empty()) {
		int t = q.front(); q.pop();
		in[t] = 0;
		for (int i = head[t]; ~i; i = edge[i].next) {
			int to = edge[i].to;
			if (edge[i].w > 0 && dis[to] > dis[t] + edge[i].c) {
				dis[to] = dis[t] + edge[i].c;
				if (!in[to]) {
					in[to] = 1;
					q.push(to);
				}
			}
		}
	}
	return dis[T] != INF;
}

int dfs(int pos, int flow) {
	if (pos == T) return flow;
	int tmp = 0, res = 0;
	vis[pos] = 1;
	for (int& i = cur[pos]; ~i; i = edge[i].next) {
		int to = edge[i].to;
		if (edge[i].w > 0 && !vis[to] && dis[to] == dis[pos] + edge[i].c) {
			tmp = dfs(to, min(flow, edge[i].w));
			if (!tmp)	continue;
			flow -= tmp;
			res += tmp;
			edge[i].w -= tmp;
			edge[i ^ 1].w += tmp;
			if (!flow) break;
		}
	}
	vis[pos] = 0;
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	memset(head, -1, sizeof head);
	cin >> n >> m >> S >> T;
	rep(i, 1, m) {
		int u, v, w, c;
		cin >> u >> v >> w >> c;
		build(u, v, w, c);
		build(v, u, 0, -c);
	}
	int ans = 0, cost = 0;
	while (spfa()) {
		rep(i, 1, n) cur[i] = head[i];
		int mf = dfs(S,INF);
		ans += mf;
		cost += dis[T] * mf;
	}
	cout << ans << ' ' << cost << endl;
	return 0;
}