2017年12月3日
最小费用最大流的一种算法:SPFA版Edmons-Karp
这里不介绍算法,只提供模板代码。所有代码基于【P3381】【模板】最小费用最大流 – 洛谷一题。
SPFA版Edmons-Karp
// Code by KSkun, 2017/12
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
struct io {
char buf[1 << 26], *s;
io() {
//freopen("p3381.in", "r", stdin);
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
const int MAXN = 100005;
const int INF = 1e9;
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev): to(to), cap(cap), cost(cost), rev(rev) {}
};
std::vector<Edge> vec[MAXN];
std::queue<int> que;
int f[MAXN];
int pre[MAXN], pree[MAXN], dis[MAXN];
bool inque[MAXN];
inline void addedge(int u, int v, int cap, int cost) {
vec[u].push_back(Edge(v, cap, cost, vec[v].size()));
vec[v].push_back(Edge(u, 0, -cost, vec[u].size() - 1));
}
// SPFA Min Cost Flow
int flow = 0, cost = 0;
inline void min_cost_flow(int s, int t) {
for(;;) {
memset(f, 0, sizeof f);
memset(dis, 0x3f, sizeof dis);
memset(inque, 0, sizeof inque);
while(!que.empty()) que.pop();
que.push(s);
dis[s] = 0;
inque[s] = true;
f[s] = INF;
while(!que.empty()) {
int u = que.front();
que.pop();
inque[u] = false;
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].to;
if(vec[u][i].cap > 0 && dis[v] > dis[u] + vec[u][i].cost) {
pre[v] = u;
pree[v] = i;
f[v] = std::min(vec[u][i].cap, f[u]);
dis[v] = dis[u] + vec[u][i].cost;
if(!inque[v]) {
que.push(v);
inque[v] = true;
}
}
}
}
if(f[t] == 0) break;
for(int u = t; u != s; u = pre[u]) {
vec[pre[u]][pree[u]].cap -= f[t];
vec[u][vec[pre[u]][pree[u]].rev].cap += f[t];
}
flow += f[t];
cost += f[t] * dis[t];
}
}
int n, m, s, t, ut, vt, wt, ct;
int main() {
n = read();
m = read();
s = read();
t = read();
for(int i = 0; i < m; i++) {
ut = read();
vt = read();
wt = read();
ct = read();
addedge(ut, vt, wt, ct);
}
min_cost_flow(s, t);
printf("%d %d", flow, cost);
return 0;
}