AcWing算法进阶课-1.17.1费用流

2023-12-25 14:35:20

算法进阶课整理

CSDN个人主页:更好的阅读体验

Start

原题链接
题目描述

给定一个包含 n n n 个点 m m m 条边的有向图,并给定每条边的容量和费用,边的容量非负。

图中可能存在重边和自环,保证费用不会存在负环。

求从 S S S T T T 的最大流,以及在流量最大时的最小费用。

输入格式

第一行包含四个整数 n , m , S , T n,m,S,T n,m,S,T

接下来 m m m 行,每行三个整数 u , v , c , w u,v,c,w u,v,c,w,表示从点 u u u 到点 v v v 存在一条有向边,容量为 c c c,费用为 w w w

点的编号从 1 1 1 n n n

输出格式

输出点 S S S 到点 T T T 的最大流和流量最大时的最小费用。

如果从点 S S S 无法到达点 T T T 则输出 0 0

数据范围

2 ≤ n ≤ 5000 2≤n≤5000 2n5000,

1 ≤ m ≤ 50000 1≤m≤50000 1m50000,

0 ≤ c ≤ 100 0≤c≤100 0c100,

? 100 ≤ w ≤ 100 -100 \le w \le 100 ?100w100

S ≠ T S≠T S=T


算法步骤

费用流算法本质上是 EK 算法,只不过将找增广路的 BFS 算法替换为了 SPFA 算法。

  1. 找到一条费用最少(最多)的增广路径
  2. 更新残量网络
  3. 累加最大流量
算法时间复杂度 O ( n m f ) O(nmf) O(nmf)

AC Code

C + + \text{C}++ 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;
}

228aa7bed3e021faf24cf8560d3e47bb.gif

最后,如果觉得对您有帮助的话,点个赞再走吧!

文章来源:https://blog.csdn.net/xingchen_2008/article/details/135197601
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。