基于 容量放缩( capacity scaling ) 的 弱多项式 最小费用最大流算法
前言
若以下内容出现了谬误,烦请私信我进行指正,以及可私信提问。
可以使用 Dijkstra 求解最短路,但需要引入类似 Primal-Dual 原始对偶和 Johnson 全源最短路的势能,复杂度
由于引入势能后同时增加常数与码长,且 SPFA 在此算法上很难卡满,因此这里使用 SPFA 求解最短路,复杂度
使用 Dijkstra 的算法可自行查看 原文献( by ouuan )。
以及笔者偶然发现了
正文
定义
代码 ( SPFA )
值得一提的是,这份代码并不能完全通过洛谷的模板,提交记录,但可以通过 UOJ 的模板。
同时,我在模板题测试了原文献的代码 Dijkstra 与 SPFA ,均不能通过,且 SPFA 表现比 Dijkstra 良好。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N = 5005, M = 1e5+5;
constexpr LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int he[N], ne[M], to[M];
LL rca[M], ca[M], co[M];
int pre[N], q[N], inq[N];
LL dis[N];
void add(int a, int b, LL c1, LL c2)
{
static int idx=2;
rca[idx] = c1, ca[idx] = 0, co[idx] = c2;
to[idx] = b, ne[idx] = he[a], he[a] = idx ++;
}
LL spfa(int s, int t)
{
int hh = 0, tt = 1;
memset(dis + 1, INF, sizeof(LL[n]));
q[0] = s, dis[s] = 0, pre[s] = 0, inq[s] = 1;
while(hh != tt)
{
int u = q[hh ++];
if(hh == N) hh = 0;
inq[u] = 0;
for(int i = he[u]; i; i = ne[i])
{
int v = to[i];
if(ca[i] && dis[v] > dis[u] + co[i])
{
dis[v] = dis[u] + co[i], pre[v] = i;
if(inq[v]) continue;
q[tt ++] = v, inq[v] = 1;
if(tt == N) tt = 0;
}
}
}
return dis[t];
}
int main()
{
int S, T;
scanf("%d%d%d%d", &n, &m, &S, &T);
for(int i = 1; i <= m; ++ i)
{
int a, b, c1, c2;
scanf("%d%d%d%d", &a, &b, &c1, &c2);
add(a, b, c1, c2), add(b, a, 0, -c2);
}
add(T, S, INF, -INF), add(S, T, 0, INF), ++ m;
for(int i = 30; i >= 0; -- i)
{
for(int j = 2; j <= (m << 1 | 1); ++ j)ca[j]<<=1;
for(int j = 2; j <= (m << 1 | 1); j += 2)
{
if(~rca[j] >> i & 1) continue;
if(ca[j]) {++ ca[j]; continue;}
int u = to[j ^ 1], v = to[j];
if(spfa(v, u) + co[j] >= 0) ++ ca[j];
else
{
++ ca[j ^ 1];
while(pre[u])
{
-- ca[pre[u]];
++ ca[pre[u] ^ 1];
u = to[pre[u] ^ 1];
}
}
}
}
LL res = 0;
for(int i = 3; i < m<<1; i += 2) res += (rca[i] - ca[i]) * co[i];
printf("%lld %lld", ca[m << 1 | 1], res);
return 0;
}