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

题目大意

最小费用最大流模板。

解题思路

模板。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信