时间戳

首页 > 技术文章 > 【模板】最小费用最大流

【模板】最小费用最大流

lyc-lb-blogs 2021-08-11 21:31 原文

【模板】最小费用最大流

题目描述

给出一个包含 $n$ 个点和 $m$ 条边的有向图（下面称其为网络） $G=(V,E)$，该网络上所有点分别编号为 $1 \sim n$，所有边分别编号为 $1\sim m$，其中该网络的源点为 $s$，汇点为 $t$，网络上的每条边 $(u,v)$ 都有一个流量限制 $w(u,v)$ 和单位流量的费用 $c(u,v)$。 你需要给每条边 $(u,v)$ 确定一个流量 $f(u,v)$，要求： 1. $0 \leq f(u,v) \leq w(u,v)$（每条边的流量不超过其流量限制）； 2. $\forall p \in \{V \setminus \{s,t\}\}$，$\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)$（除了源点和汇点外，其他各点流入的流量和流出的流量相等）； 3. $\sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)$（源点流出的流量等于汇点流入的流量）。 定义网络 $G$ 的流量 $F(G)=\sum_{(s,i)\in E}f(s,i)$，网络 $G$ 的费用 $C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)$。 你需要求出该网络的**最小费用最大流**，即在 $F(G)$ 最大的前提下，使 $C(G)$ 最小。

输入输出格式

输入格式

 

输入第一行包含四个整数 $n,m,s,t$，分别代表该网络的点数 $n$，网络的边数 $m$，源点编号 $s$，汇点编号 $t$。 接下来 $m$ 行，每行四个整数 $u_i,v_i,w_i,c_i$，分别代表第 $i$ 条边的起点，终点，流量限制，单位流量费用。

输出格式

 

输出两个整数，分别为该网络的最大流 $F(G)$，以及在 $F(G)$ 最大的前提下，该网络的最小费用 $C(G)$。

输入输出样例

输入样例 #1

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

输出样例 #1

50 280

说明

对于 $100\%$ 的数据，$1 \leq n \leq 5\times 10^3$，$1 \leq m \leq 5 \times 10^4$，$1 \leq s,t \leq n$，$u_i \neq v_i$，$0 \leq w_i,c_i \leq 10^3$，且该网络的最大流和最小费用 $\leq 2^{31}-1$。 输入数据随机生成。
 
 
 


#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1e5 + 10;

int h[N], ne[N], e[N], w[N], val[N], idx;

int dis[N], pre[N], last[N], flow[N];
bool st[N];
void add(int a,int b,int c,int d)
{
	e[idx] = b; w[idx] = c; ne[idx] = h[a]; val[idx] = d; h[a] = idx++;
}
int n, m ,S ,T;

int maxflow, mincost;
bool spfa()
{
	queue  q;
	q.push(S);
	memset(dis, 0x7f, sizeof dis);
	memset(flow, 0x7f, sizeof flow);
	memset(st , 0, sizeof st);
	st[S] = 1;	dis[S] = 0; pre[T] = -1;
	
	while(q.size())
	{
		int t = q.front();
		q.pop();
		st[t] = 0;
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(w[i] > 0 && dis[j] > dis[t] + val[i])
			{
				dis[j] = dis[t] + val[i];
				pre[j] = t;
				last[j] = i;
				flow[j] = min(flow[t], w[i]);
				if(!st[j])
				{
					st[j] = 1;
					q.push(j);
				}
			}
		}
	}
	
	return pre[T] != -1;
	
}

void work()
{
	while(spfa())
	{
		int now = T;
		maxflow += flow[T];
		mincost += flow[T] * dis[T];
		while(now != S)
		{
			w[last[now]] -= flow[T];
			w[last[now] ^ 1] += flow[T];
			now = pre[now];
		}
	}
}

int main()
{
	scanf("%d %d %d %d", &n, &m, &S, &T);
	memset(h, -1 ,sizeof h);
	for(int i = 1 ; i <= m; i++)
	{
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		
		add(a, b, c, d);
		add(b, a, 0, -d);
	}
	
	work();
	printf("%d %d", maxflow, mincost);
	return 0;
}

推荐阅读