博客

模板提

P3381 【模板】最小费用最大流

个人简述

首先呢，dijkstra算法求费用流是不如spfa求费用流的，因为这个题目不开O2优化，就过不去….

那么我们为什么要用这个算法呢？个人认为确实没什么用….还是用spfa或者zkw求费用流吧

总所周知，dijkstra是不能跑有负环的图的，而我们在求最小费用流的过程中一般会存在负环（反边的存在），因此我通过引入势的概念，将图的边用 e’ 代替，其中 e’ = e + h[u] – h[v] ，h[i]代表i点的势，这样的话，将新的图中的s-t路径的长度减去常数h[s] – h[t] ，得到的即为原图中对应路径的长度，因此新图和原图中的最短路是一致的。

因为dijkstra只实用于无负环的图，所以我们需要选取合适的势，将使得新图的每一条边的费用 cost[e] >= 0，我们就可以用dijkstra算法求最小费用流了。

代码区

#pragma GCC optimize(2)			//O2优化，不开过不去...
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip>
#define bug cout << "**********" << endl
#define show(x,y) cout<<"["<<x<<","<<y<<"] "
//#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int Max = 5e3 + 10;

struct Edge
{
	int to, rev;					//rev记录反向边
	int flow, cost;;
};

int n, m, k;
vector<Edge>edge[Max << 1];
int h[Max];							//每个结点的势
int dis[Max];
int pre_node[Max], pre_edge[Max];	//前驱结点和对应边

void add(int u, int v, int flow, int cost)
{
	edge[u].push_back({ v,(int)edge[v].size(),flow,cost });

	edge[v].push_back({ u,(int)edge[u].size() - 1,0,-cost });
}

void min_cost_flow(int s, int t, int& min_cost, int& max_flow)
{
	fill(h + 1, h + 1 + n, 0);
	min_cost = max_flow = 0;
	int tot = inf;							//源点流量无限
	while (tot > 0)
	{
		priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
		memset(dis, inf, sizeof(dis));
		dis[s] = 0;q.push({ 0,s });
		while (!q.empty())
		{
			int u = q.top().second;
			int dist = q.top().first;
			q.pop();
			if (dis[u] < dist)continue;		//当前的距离不是最近距离
			for (int i = 0;i < edge[u].size(); i++)
			{
				Edge &e = edge[u][i];
				if (edge[u][i].flow > 0 && dis[e.to] > dis[u] + e.cost + h[u] - h[e.to])
				{
					dis[e.to] = dis[u] +e.cost + h[u] - h[e.to];
					pre_node[e.to] = u;
					pre_edge[e.to] = i;
					q.push({ dis[e.to],e.to });
				}
			}
		}
		if (dis[t] == inf)break;			//无法增广了
		for (int i = 1;i <= n;i++) h[i] += dis[i];
		int flow = tot;						//求这一增广路径的流量
		for (int i = t; i != s; i = pre_node[i])
			flow = min(flow, edge[pre_node[i]][pre_edge[i]].flow);
		for (int i = t; i != s; i = pre_node[i])
		{
			Edge& e = edge[pre_node[i]][pre_edge[i]];
			e.flow -= flow;
			edge[i][e.rev].flow += flow;
		}
		tot -= flow;
		max_flow += flow;
		min_cost += flow * h[t];
	}
}

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int s, t;
	while (scanf("%d%d%d%d", &n, &m, &s, &t) != EOF)
	{
		for (int i = 1, u, v, flow, cost;i <= m;i++)
		{
			scanf("%d%d%d%d", &u, &v, &flow, &cost);
			add(u, v, flow, cost);
		}
		int min_cost, max_flow;
		min_cost_flow(s, t, min_cost, max_flow);
		printf("%d %d\n", max_flow, min_cost);
	}
	return 0;
}