参考博客:
https://www.luogu.com.cn/blog/Mogician/Network-Flow-Guide
可以先了解了解johnson全源最短路算法。
核心思想为给每个点一个顶标,改边权为(h[x]+w-h[y])。
如果顶标设的好(设为最短路),就可以保证边权非负,然后跑dij。
这个可以套在最小费用最大流上面,问题在于不可能每次流之后都重新跑spfa求最短路。
而解决方法是给所有点的h加上这一次的最短路的dis,通过推理可以证明这是对的,详见参考博客。
如果是最大费用,把一开始的边权取负即可(不考虑要消圈的话)。
板子:
https://www.luogu.com.cn/problem/P3381
Code:
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int N = 1e6 + 5;
int n, m, S, T;
int x, y, z1, z2;
int fi[N], to[N], nt[N], r[N], w[N], tot = 1;
void link(int x, int y, int z1, int z2) {
nt[++ tot] = fi[x], to[tot] = y, r[tot] = z1, w[tot] = z2, fi[x] = tot;
nt[++ tot] = fi[y], to[tot] = x, r[tot] = 0, w[tot] = -z2, fi[y] = tot;
}
const int inf = 1e9;
int d[N], d0, dis[N], bz[N];
void spfa() {
fo(i, 1, n) dis[i] = inf;
dis[S] = 0; d[d0 = 1] = S; bz[S] = 1;
for(int i = 1; i <= d0; i ++) {
int x = d[i]; bz[x] = 0;
for(int j = fi[x]; j; j = nt[j]) if(r[j]) {
int y = to[j];
if(dis[x] + w[j] < dis[y]) {
dis[y] = dis[x] + w[j];
if(!bz[y]) bz[y] = 1, d[++ d0] = y;
}
}
}
}
int h[N];
struct P {
int x, y;
P(int _x = 0, int _y = 0) {
x = _x, y = _y;
}
};
bool operator < (P a, P b) { return a.y > b.y;}
int fr[N];
priority_queue<P> q;
int us[N];
ll ans1 = 0, ans = 0;
int dij() {
while(!q.empty()) q.pop();
fo(i, 1, n) dis[i] = inf, fr[i] = 0, us[i] = 0;
dis[S] = 0;
q.push(P(S, dis[S]));
while(q.size()) {
P b;
while(q.size()) {
b = q.top(); q.pop();
if(!us[b.x]) break;
}
if(us[b.x]) continue;
us[b.x] = 1;
for(int j = fi[b.x]; j; j = nt[j]) if(r[j]) {
int y = to[j];
int z = b.y + h[b.x] + w[j] - h[y];
if(z < dis[y]) {
fr[y] = j;
dis[y] = z;
q.push(P(y, dis[y]));
}
}
}
if(dis[T] == inf) return 0;
int mi = inf;
for(int p = T; p != S; p = to[fr[p] ^ 1]) mi = min(mi, r[fr[p]]);
ans1 += mi;
for(int p = T; p != S; p = to[fr[p] ^ 1]) {
ans += w[fr[p]] * mi;
r[fr[p]] -= mi, r[fr[p] ^ 1] += mi;
}
fo(i, 1, n) if(dis[i] < inf)
h[i] += dis[i];
return 1;
}
int main() {
scanf("%d %d %d %d", &n, &m, &S, &T);
fo(i, 1, m) {
scanf("%d %d %d %d", &x, &y, &z1, &z2);
link(x, y, z1, z2);
}
spfa();
fo(i, 1, n) h[i] = dis[i];
while(dij());
pp("%lld %lld
", ans1, ans);
}