算法进阶课整理
CSDN个人主页:更好的阅读体验
原题链接
题目描述
给定一个包含 $n$ 个点 $m$ 条边的有向图,并给定每条边的容量和费用,边的容量非负。
图中可能存在重边和自环,保证费用不会存在负环。
求从 $S$ 到 $T$ 的最大流,以及在流量最大时的最小费用。
输入格式
第一行包含四个整数 $n,m,S,T$。
接下来 $m$ 行,每行三个整数 $u,v,c,w$,表示从点 $u$ 到点 $v$ 存在一条有向边,容量为 $c$,费用为 $w$。
点的编号从 $1$ 到 $n$。
输出格式
输出点 $S$ 到点 $T$ 的最大流和流量最大时的最小费用。
如果从点 $S$ 无法到达点 $T$ 则输出 0 0
。
数据范围
$2≤n≤5000$,
$1≤m≤50000$,
$0≤c≤100$,
$-100 \le w \le 100$
$S≠T$
算法步骤
费用流算法本质上是 EK 算法,只不过将找增广路的 BFS 算法替换为了 SPFA 算法。
- 找到一条费用最少(最多)的增广路径
- 更新残量网络
- 累加最大流量
算法时间复杂度 $O(nmf)$
AC Code
$\text{C}++$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010, M = 100010;
const int INF = 1e9;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], w[M], idx;
int q[N], d[N], pre[N], lim[N];
bool st[N];
inline void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}
bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(lim, 0, sizeof lim);
q[0] = S, d[S] = 0, lim[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > d[t] + w[i] && f[i])
{
d[j] = d[t] + w[i];
pre[j] = i, lim[j] = min(f[i], lim[t]);
if (!st[j])
{
st[j] = true;
q[tt ++ ] = j;
if (tt == N) tt = 0;
}
}
}
}
return lim[T] > 0;
}
void EK(int& flow, int& cost)
{
while (spfa())
{
int t = lim[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
f[pre[i]] -= t, f[pre[i] ^ 1] += t;
}
}
int main()
{
int a, b, c, d;
memset(h, -1, sizeof h);
scanf("%d%d%d%d", &n, &m, &S, &T);
while (m -- )
{
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
}
int flow = 0, cost = 0;
EK(flow, cost);
printf("%d %d\n", flow, cost);
return 0;
}
最后,如果觉得对您有帮助的话,点个赞再走吧!
what is f?
in 时间复杂度
最大流的流量