一类带负圈的最小费用流

First Post:

Last Update:

之前复习网络流的时候好像没有复习扎实，把这玩意漏掉了。

事实证明，“就看看而不写代码”确实挺容易忘的。

注意：下文所讨论的流都允许一个与 不相连的环出现。

下文的四元组 表示一条从 到 ，流量为 ，费用为 的边。

一般不带负圈的最小费用流，大家使用自己喜欢的方式就跑过去了。

但是带负圈的最小费用流，会给最短路算法带来极大的困难，导致增广出现问题。

我们就需要一个办法，把图里的负权边都去掉。

注意到我们在建网络流图的时候，会对称地建一条反着的边，费用为原边权的相反数，表示退流。

那么我们在这里，能不能先把负权边都流满，然后借助反向的正权边来完成”退流“工作呢？

显然是可以的。

对于一条负权边 ，我们先把该边流满，将答案预先加上 ，然后建出反向边 ，用以退流。

但这种做法还有一个问题，即所有负权边满流的网络，不一定满足流量平衡的限制。

设原图源汇为 ，我们新建虚拟源点、虚拟汇点 ，用 跑遍网络流，来满足流量平衡的限制。

具体地，假设我们处理了一条负权边 ，那么 点就应该多流入 的流量， 点应该多流出 的流量，我们通过连边 来表达这两个限制，因为最后基于 跑出来的网络流是流量平衡的，我们把这里连的虚拟边删掉，就正好满足 点多流入 ， 点多流出 。

所以，对于一条负权边，我们会将其拆为三条边 。然后我们先以 为源点， 为汇点，跑一遍网络流。在残量网络上，忽略与 和 相邻的边，再以 和 为源汇，跑一遍网络流，将两遍网络流得到的答案相加即可。

需要注意的是，就算原图中没有源汇，这个方法也是可行的，此时这个问题被叫做最小费用循环流（或者说最小费用可行流）。

此时，在原问题中，我们一次会增广一个环，假设这个环除了某条负权边 外，剩下的边费用为 。

如果 ，那么这个负环需要增广，在新图上，有 那么我们会倾向与走剩下的那条路径，也就是不退流。反之，因为是正环，所以我们会倾向于不增广，在新图上就是走这条 ，把流退掉。

这样可以从另一个方面理解其正确性。

需要注意的是，在求解循环流的时候，需要注意原题面有没有限制流量上界。有的话，在通过 增广时就要加以限制。

事实上，如果读者对上下界网络流较为熟悉，应该能看出来，这就是对上下界网络流的一种应用。

附上模板题代码：

洛谷 P7173

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 5;
typedef long long ll;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
int n,m,S,T;
int num[N];
namespace Flow{
	const int N = 2e3 + 5,M = 2e6 + 5;
	int fir[N],nxt[M],to[M],w[M],cost[M],ect = 1;
	inline void addedge(int u1,int v1,int w1,int c1)
	 { nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;w[ect] = w1;cost[ect] = c1;}
	inline void ins(int u1,int v1,int w1,int c1) { addedge(u1,v1,w1,c1);addedge(v1,u1,0,-c1);}
	ll dis[N],h[N];
	bool vst[N];
	int tot;
	inline void Clr(int _n)
	{
		tot = _n;ect = 1;
		for(int i = 1;i <= tot;i++) fir[i] = 0;
	}
	void spfa(int S,int T)
	{
		for(int i = 1;i <= tot;i++) dis[i] = llinf,vst[i] = 0;
		queue<int> Q;
		Q.push(S);dis[S] = 0;vst[S] = 1;
		while(!Q.empty())
		{
			int x = Q.front();Q.pop();vst[x] = 0;
			for(int i = fir[x],y;y = to[i],i;i = nxt[i])
				if(w[i] && dis[y] > dis[x] + cost[i])
				{
					dis[y] = dis[x] + cost[i];
					if(!vst[y]) Q.push(y),vst[y] = true;
				} 
		}
		for(int i = 1;i <= tot;i++) h[i] = dis[i];
	}
	int pn[N],pe[N],flow[N];
	struct node{
		int id;ll dis;
		node(){}
		node(const int _id,const ll _dis):id(_id),dis(_dis){}
		bool operator < (const node &rhs) const { return dis > rhs.dis;}
	};
	bool Dijkstra(int S,int T,int F = 1e9)
	{
		for(int i = 1;i <= tot;i++)
			pe[i] = pn[i] = vst[i] = 0,dis[i] = llinf;
		priority_queue<node> Q;
		flow[S] = F;Q.emplace(S,dis[S] = 0);
		while(!Q.empty())
		{
			int x = Q.top().id;Q.pop();
			if(vst[x]) continue;
			vst[x] = true;
			for(int i = fir[x],y,ww;y = to[i],ww = cost[i] + h[x] - h[y],i;i = nxt[i])
				if(w[i] && dis[y] > dis[x] + ww)
				{
					dis[y] = dis[x] + ww;
					pn[y] = x;pe[y] = i;flow[y] = min(flow[x],w[i]);
					Q.emplace(y,dis[y]);
				}
		}
		return dis[T] < llinf;
	}
	pair<ll,ll> MCMF(int S,int T)
	{
		ll F = 0,res = 0;
		spfa(S,T);
		while(Dijkstra(S,T))
		{
			for(int i = 1;i <= tot;i++) if(vst[i]) h[i] += dis[i];
			int now = T;
			res += flow[T] * h[T];
			while(now != S)
				w[pe[now]] -= flow[T],w[pe[now] ^ 1] += flow[T],now = pn[now];
			F += flow[T];
		}
		return make_pair(F,res);
	}
}
ll ans = 0;
int main()
{
	cin >> n >> m >> S >> T;
	Flow::Clr(n + 2);
	for(int i = 1;i <= m;i++)
	{
		int x,y,f,c;
		cin >> x >> y >> f >> c;
		if(c >= 0)
			Flow::ins(x,y,f,c);
		else
		{
			num[x] -= f;num[y] += f;
			Flow::ins(y,x,f,-c);
			ans += 1ll * c * f;
		}
	}
	int SS = n + 1,TT = n + 2;
	for(int i = 1;i <= n;i++)
	{
		if(num[i] > 0) Flow::ins(SS,i,num[i],0);
		if(num[i] < 0) Flow::ins(i,TT,-num[i],0);
	}
	ans += Flow::MCMF(SS,TT).second;
	pair<ll,ll> res = Flow::MCMF(S,T);
	cout << res.first << ' ' << res.second + ans << endl;
	return 0;
}
≡