最小费用最大流 dijkstra 版本

本文主要是介绍最小费用最大流 dijkstra 版本，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

引入

一个优秀的代码，时间复杂度一定是很优的， SPFA + EK/dinic 已经满足不了我们的需求了，所以~~吃饱了撑着的~~善于思考的人类不断地探索发现，一个更加优化的算法就此诞生。

详解

考虑之前的 SPFA + EK/dinic 算法，我们发现让我们被卡的飞起的地方就是 SPFA 那个**的 \(O(nm)\) 时间复杂度，所以我们迫切地需要一个更快，更高效的算法来解决这个问题。考虑到比 SPFA 快的单元最短路算法 dijkstra 不能跑负边，所以我们需要对其进行改进。
考虑对于每一个点都附上一个权值 \(pe(i)\) 再将每条边 (假设为 \(u->v\) ) 的权值变为 \(w(u, v) + pe(u) - pe(v)\) 我们可以发现，在中间点的权值就被抵消掉了，只剩下了起点和终点，也就是说最短路选的路径没有变，但是最短路的值加上了 \(pe(s)\) 减去了 \(pe(t)\) ，当然，这对网络流里求增广路没有影响。如果我们的 \(w(u, v) + pe(u) - pe(v)\) 都非负，我们的 dijkstra 就活过来了。
那么，我们如何让其非负呢？
~~通过大量实验~~经过严谨的推理后我们发现将起点到某个点 \(v\) ，的 \(pe(v)\) 是一个很好的解决方案。因为对于一个点 \(v\) 来说，所有指向它的点 \(u\) 都有 \(pe(u) + w(u, v) \le pe(v)\) 否则 \(pe(v)\) 就不是最短路了。
但这以后又有了一个新的问题，我们的网络流每次增广后都会产生图的改变，那么我们所求的最开始的最短路也就可能出现问题，如果这样的话，我们每次都要用可以跑负边的 SPFA 去跑一次最短路，那么 dijkstra 也就失去了意义。
这又如何解决呢？
其实也并不难。我们最开始需要跑一次 SPFA 来找到最短路（相比于网络流，一次的时间还是不算什么的）。接下来我们考虑第一次增广的 \(pe(i)\) 是已经找出来的，那么直接进行此次增广后可能会出现有边反向，但此时我们先不管它，因为这些反向的边都是在最短路上的，所以如果存在 \(u->v\) 反向，那么因为刚才的保证了 \(pe(u) - pe(v) + w (u, v) \ge 0\) 的，那么 \(pe(v) + (-w(u, v)) \ge pe(u)\) 也是成立的，也就是说经过这条反边是不会改变 \(pe(u)\) 的，那么 \(pe(u)\) 可以继续沿用。也就是说我们每次寻找最短路的 \(pe(i)\) 都可以直接用上一次增广时使用的最短路，而上一次增广路是直接用 \(dijkstra\) 求出来的，也就是增广时顺便求出的。
这样我们就完成了整个算法的讲解

补充

在各类资料中，我们都将这里的 \(pe(i)\) 称作势能，这个东西其实挺牛逼的， \(Johnson 全源最短路径算法\) 也是通过这个方法将边全变为正，然后再用 dijkstra 跑 \(n\)次单元最短路，最后做出了 \(O(n^2mlogm)\) 的多元最短路。
对于这个费用流的算法，其实实际测出来并不算快，而且莫名的特别吃 \(O2\) ，不过比较稳定，很少能被数据直接卡升天。虽然还是有数据会将其卡飞，不过毕竟少了。
最后，这里再引出一个算法，后面可能也会写，就是原始对偶算法，这个算法听说是网络流的最快算法

代码

废话了这么多，我知道这应该是你们最期待的
开 \(O2\) 跑飞快，不开 T 1点的 dinic 版本：

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define MAXN 50000
#define MAXM 500000

template <typename type, typename costtype, int maxn, int maxm, type inf>
class SSP {
	public:
		type sv[maxm];
	private:
		int H, T;
		struct node {
			int ed;
			node *next;
			int lo;
		}se[maxm];
		costtype scost[maxm];
		node *sn[maxn];
		node *si[maxn];
		costtype pl[maxn];
		costtype pe[maxn];
		int tot;
		bool vis[maxn];
	
	private:
		void push_edge (int u, int v, type value, costtype cost) {
			node *p = &se[tot];
			
			p->ed = v;
			scost[tot] = cost;
			sv[tot] = value;
			p->lo = tot;
			p->next = sn[u];
			sn[u] = p;
			tot ++;
		}
		type dfs (int now, type cap) {
			vis[now] = 1;
			if (now == T) {
				vis[now] = 0;
				
				return cap;
			}
			
			type num = 0;
			
			for (; si[now]; si[now] = si[now]->next) {
				if (pl[si[now]->ed] + scost[si[now]->lo] + pe[si[now]->ed] - pe[now] == pl[now] && sv[si[now]->lo] && !vis[si[now]->ed]) {
					type sum = dfs (si[now]->ed, min (cap - num, sv[si[now]->lo]));
					
					sv[si[now]->lo] -= sum;
					sv[si[now]->lo ^ 1] += sum;
					num += sum;
					if (num == cap) {
						vis[now] = 1;
						
						return cap;
					}
				}
			}
			vis[now] = 0;
			
			return num;
		}
		pair <type, costtype> dinic (int n) {
			if (H == T) {
				return make_pair(inf, inf);
			}
			
			priority_queue <pair <costtype, int>, vector <pair <costtype, int> >, greater<pair <costtype, int> > > q;
			
			for (int i = 1; i <= n; i ++) {
				pl[i] = inf;
				vis[i] = 0;
			}
			pl[T] = 0;
			q.push(make_pair (0, T));
			while (!q.empty()) {
				int l = q.top().second;
				
				q.pop();
				if (vis[l]) {
					continue;
				}
				si[l] = sn[l];
				vis[l] = 1;
				for (node *i = sn[l]; i; i = i->next) {
					if (sv[i->lo ^ 1] == 0) {
						continue;
					}
					if (scost[i->lo ^ 1] + pl[l] + pe[l] - pe[i->ed] < pl[i->ed]) {
						pl[i->ed] = scost[i->lo ^ 1] + pl[l] + pe[l] - pe[i->ed];
						q.push(make_pair (pl[i->ed], i->ed));
					}
				}
			}
			if (pl[H] < inf) {
				for (int i = 1; i <= n; i ++) {
					vis[i] = 0;
				}
				
				type cap = dfs (H, inf);
				costtype cost = cap * (pl[H] + pe[H]);
				
				return make_pair (cap, cost);
			}
			
			return make_pair (0, 0);
		}
	public:
		void clear () {
			tot = 0;
			for (int i = 1; i <= maxn; i ++) {
				sn[i] = 0;
			}
		}
		void push (int u, int v, type value, costtype cost) {
			push_edge (u, v, value, cost);
			push_edge (v, u, 0, -cost);
		}
		pair<type, costtype> maxflow (int h, int t, int n){
			H = h;
			T = t;
			
			pair <type, costtype> ans = make_pair (0, 0);
			
			queue <int> q;
			
			for (int i = 1; i <= n; i ++) {
				pe[i] = inf;
				vis[i] = 0;
			}
			pe[T] = 0;
			q.push (T);
			vis[T] = 1;
			while (!q.empty ()) {
				int now = q.front ();
		
				q.pop ();
				vis[now] = 0;
				for (node *i = sn[now]; i; i = i->next) {
					if (sv[i->lo ^ 1] && pe[i->ed] > pe[now] + scost[i->lo ^ 1]) {
						pe[i->ed] = pe[now] + scost[i->lo ^ 1];
						if (!vis[i->ed]) {
							vis[i->ed] = 1;
							q.push (i->ed);
						}
					}
				}
			}
			while (1) {
				pair<type, costtype> num = dinic (n);
				
				ans.first += num.first;
				ans.second += num.second;
				if (!num.first) {
					break;
				}
				for (int i = 1; i <= n; i ++) {
					pe[i] += pl[i];
				}
			}
			
			return ans;
		}
		type limited_maxflow (int h, int t, int n, costtype limit) {
			H = h;
			T = t;
			
			pair <type, costtype> ans = make_pair (0, 0);
			
			queue <int> q;
			
			for (int i = 1; i <= n; i ++) {
				pe[i] = inf;
				vis[i] = 0;
			}
			pe[T] = 0;
			q.push (T);
			vis[T] = 1;
			while (!q.empty ()) {
				int now = q.front ();
		
				q.pop ();
				vis[now] = 0;
				for (node *i = sn[now]; i; i = i->next) {
					if (sv[i->lo ^ 1] && pe[i->ed] > pe[now] + scost[i->lo ^ 1]) {
						pe[i->ed] = pe[now] + scost[i->lo ^ 1];
						if (!vis[i->ed]) {
							vis[i->ed] = 1;
							q.push (i->ed);
						}
					}
				}
			}
			while (1) {
				pair<type, costtype> num = dinic (n);
				
				if (ans.second + num.second > limit) {
					ans.first += (limit - ans.second) / (num.second / num.first);
					
					break;
				}
				ans.first += num.first;
				ans.second += num.second;
				if (!num.first) {
					break;
				}
				for (int i = 1; i <= n; i ++) {
					pe[i] += pl[i];//注意， pl跑出来是最短路减去刚才的pe， 所以直接加
				}
			}
			
			return ans.first;
		}
};
SSP <long long, long long, MAXN + 5, MAXM + 5, 0x3f3f3f3f3f3f3f3f> ssp;
int main () {
	int n, m, h, t;
	
	scanf ("%d %d %d %d", &n, &m, &h, &t);
	for (int i = 1; i <= m; i ++) {
		int u, v;
		long long w, c;
		
		scanf ("%d %d %lld %lld", &u, &v, &w, &c);
		ssp.push(u, v, w, c);
	}
	
	pair <long long, long long> ans = ssp.maxflow(h, t, n);
	
	printf ("%lld %lld", ans.first, ans.second);
}

直接跑就能过，开 \(O2\) 却没有那么快的 EK 版本：

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define MAXN 50000
#define MAXM 500000

template <typename type, typename costtype, int maxn, int maxm, type inf>
class SSP {
	public:
		type sv[maxm];
	private:
		int H, T;
		struct node {
			int ed;
			node *next;
			int lo;
		}se[maxm];
		struct Last {
			int ed;
			int nd;
		}last[maxn];
		costtype scost[maxm];
		node *sn[maxn];
		node *si[maxn];
		costtype pl[maxn];
		costtype pe[maxn];
		int tot;
		bool vis[maxn];
	
	private:
		void push_edge (int u, int v, type value, costtype cost) {
			node *p = &se[tot];
			
			p->ed = v;
			scost[tot] = cost;
			sv[tot] = value;
			p->lo = tot;
			p->next = sn[u];
			sn[u] = p;
			tot ++;
		}
		pair <type, costtype> EK (int n) {
			if (H == T) {
				return make_pair(inf, inf);
			}
			
			priority_queue <pair <costtype, int>, vector <pair <costtype, int> >, greater<pair <costtype, int> > > q;
			
			for (int i = 1; i <= n; i ++) {
				pl[i] = inf;
				vis[i] = 0;
				last[i].ed = 0;
				last[i].nd = 0;
			}
			pl[T] = 0;
			q.push(make_pair (0, T));
			while (!q.empty()) {
				int l = q.top().second;
				
				q.pop();
				if (vis[l]) {
					continue;
				}
				si[l] = sn[l];
				vis[l] = 1;
				for (node *i = sn[l]; i; i = i->next) {
					if (sv[i->lo ^ 1] == 0) {
						continue;
					}
					if (scost[i->lo ^ 1] + pl[l] + pe[l] - pe[i->ed] < pl[i->ed]) {
						last[i->ed].nd = l;
						last[i->ed].ed = (i->lo ^ 1);
						pl[i->ed] = scost[i->lo ^ 1] + pl[l] + pe[l] - pe[i->ed];
						q.push(make_pair (pl[i->ed], i->ed));
					}
				}
			}
			if (pl[H] < inf) {
				for (int i = 1; i <= n; i ++) {
					vis[i] = 0;
				}
				
				type cap = inf;
				
				for (int i = H; i != T; i = last[i].nd) {
					cap = min (cap, sv[last[i].ed]);
				}
				for (int i = H; i != T; i = last[i].nd) {
					sv[last[i].ed] -= cap;
					sv[last[i].ed ^ 1] += cap;
				}
				
				costtype cost = cap * (pl[H] + pe[H]);
				
				return make_pair (cap, cost);
			}
			
			return make_pair (0, 0);
		}
	public:
		void clear () {
			tot = 0;
			for (int i = 1; i <= maxn; i ++) {
				sn[i] = 0;
			}
		}
		void push (int u, int v, type value, costtype cost) {
			push_edge (u, v, value, cost);
			push_edge (v, u, 0, -cost);
		}
		pair<type, costtype> maxflow (int h, int t, int n){
			H = h;
			T = t;
			
			pair <type, costtype> ans = make_pair (0, 0);
			
			queue <int> q;
			
			for (int i = 1; i <= n; i ++) {
				pe[i] = inf;
				vis[i] = 0;
			}
			pe[T] = 0;
			q.push (T);
			vis[T] = 1;
			while (!q.empty ()) {
				int now = q.front ();
		
				q.pop ();
				vis[now] = 0;
				for (node *i = sn[now]; i; i = i->next) {
					if (sv[i->lo ^ 1] && pe[i->ed] > pe[now] + scost[i->lo ^ 1]) {
						pe[i->ed] = pe[now] + scost[i->lo ^ 1];
						if (!vis[i->ed]) {
							vis[i->ed] = 1;
							q.push (i->ed);
						}
					}
				}
			}
			while (1) {
				pair<type, costtype> num = EK (n);
				
				ans.first += num.first;
				ans.second += num.second;
				if (!num.first) {
					break;
				}
				for (int i = 1; i <= n; i ++) {
					pe[i] += pl[i];
				}
			}
			
			return ans;
		}
		type limited_maxflow (int h, int t, int n, costtype limit) {
			H = h;
			T = t;
			
			pair <type, costtype> ans = make_pair (0, 0);
			
			queue <int> q;
			
			for (int i = 1; i <= n; i ++) {
				pe[i] = inf;
				vis[i] = 0;
			}
			pe[T] = 0;
			q.push (T);
			vis[T] = 1;
			while (!q.empty ()) {
				int now = q.front ();
		
				q.pop ();
				vis[now] = 0;
				for (node *i = sn[now]; i; i = i->next) {
					if (sv[i->lo ^ 1] && pe[i->ed] > pe[now] + scost[i->lo ^ 1]) {
						pe[i->ed] = pe[now] + scost[i->lo ^ 1];
						if (!vis[i->ed]) {
							vis[i->ed] = 1;
							q.push (i->ed);
						}
					}
				}
			}
			while (1) {
				pair<type, costtype> num = EK (n);
				
				if (ans.second + num.second > limit) {
					ans.first += (limit - ans.second) / (num.second / num.first);
					
					break;
				}
				ans.first += num.first;
				ans.second += num.second;
				if (!num.first) {
					break;
				}
				for (int i = 1; i <= n; i ++) {
					pe[i] += pl[i];
				}
			}
			
			return ans.first;
		}
};
SSP <long long, long long, MAXN + 5, MAXM + 5, 0x3f3f3f3f3f3f3f3f> ssp;
int main () {
	int n, m, h, t;
	
	scanf ("%d %d %d %d", &n, &m, &h, &t);
	for (int i = 1; i <= m; i ++) {
		int u, v;
		long long w, c;
		
		scanf ("%d %d %lld %lld", &u, &v, &w, &c);
		ssp.push(u, v, w, c);
	}
	
	pair <long long, long long> ans = ssp.maxflow(h, t, n);
	
	printf ("%lld %lld", ans.first, ans.second);
}

这篇关于最小费用最大流 dijkstra 版本的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

最小费用最大流 dijkstra 版本

引入

详解

补充

代码

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯