最大流

求解方法

有两种，第一种是 EK 算法，就是每一找到一条增广路径然后加上这条边的贡献。

EK，傻逼算法！ —— uob&yny

相关法律规定，网络A流题随便卡 EK，因为它的时间复杂度是 O(VE2)O(VE^2) 的，效率过于低下。

所以就诞生了另一种增广路算法：Dinic 算法。

Dinic 算法类似于 EK 的多路增广版本，但是有一个非常关键的优化：当前弧优化。这个优化针对多路增广时重复遍历到某一个节点时，因为我们已经知道走某一些边已经不能再增广了，所以可以记录一下当前走到那个边了，然后从这个边进行增广即可。

时间复杂度为 O(V2E)O(V^2E)，在某些图上有更优的复杂度，如二分图上有 O(EV)O(E\sqrt V) 的优秀复杂度。

目前较好的一种实现，容易写假的地方会标出。

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
#include<bits/stdc++.h>
using namespace std;
// #define int long long
struct line{
	int to,link;
	long long flow;
}E[10005];
int head[205],tot=1;
inline void addE(const int u,const int v,const int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	head[u]=tot;
	return;
}
int s,t,n,m;
int dis[205],vis[205],cur[205];
queue<int> q;
inline bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=(1<<30),vis[i]=0;
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		const int u=q.front();
		q.pop();
		vis[u]=1;
		for(int i=head[u];i;i=E[i].link){
			if(E[i].flow&&dis[E[i].to]>dis[u]+1){
				dis[E[i].to]=dis[u]+1;
				if(!vis[E[i].to]){
					q.push(E[i].to);
				}
			}
		}
	}
	return dis[t]!=(1<<30);
}
long long dfs(const int &now,const long long &maxflow){
	if(maxflow==0||now==t)return maxflow;
	long long nowflow=0;
// 	vis[now]=1;//不需要 vis 是因为bfs的时候最短路对于某个方向是单调递增的。
    //加了 vis 数组反而容易写假。而且其实上面的 bfs 也是可以省掉 vis 数组的，原理是一样的。
    //但是注意不要与费用流搞混了。
// 	assert(cur[now]==0||cur[now]==head[now]);
	for(int &i=cur[now];i;i=E[i].link){
		if(dis[E[i].to]==dis[now]+1){
			const long long flow=dfs(E[i].to,min(E[i].flow,maxflow-nowflow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				if(maxflow==nowflow)break;
			}
		}
	}
// 	vis[now]=0;
	return nowflow;
}
inline long long dinic(){
	long long res=0;
	while(bfs()){
		for(int i=1;i<=n;i++)cur[i]=head[i],vis[i]=0;
		res+=dfs(s,1e18); 
		// exit(0);
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("1.in","r",stdin);
	cin>>n>>m>>s>>t;
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		addE(x,y,z);
		addE(y,x,0);
	}
	cout<<dinic();
	return 0;
}

一些例题

P3163 危桥

考虑对原来的岛屿建出双向边。把来回看做去一次并原路返回一次，那么危桥的容量就是 11，普通桥的容量就是 +∞+\infty。

一个 trival 的想法是，就直接源点连接两个起始点 a1,b1a_1,b_1，权值为 an,bna_n,b_n，a2,b2a_2,b_2 连接汇点，权值同源点。但是这样跑出来有可能一些流量是 a1→b2a_1\to b_2 或 a2→b1a_2\to b_1 的，此时我们不难发现跑一遍 S→a1,b2S\to a_1,b_2，T→a2,b1T\to a_2,b_1，此时原来的 a1→b2a_1\to b_2 的流量可以和 b2→a2b_2\to a_2 的流量配对，另外一种是一样的。那么就能满足原题限制。所以要保证两次都满流才能保证有解。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// Problem: P3163 [CQOI2014] 危桥
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3163
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-10 15:44:30
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct line{
	int to,link,flow;
}E[200005];
int head[62505],tot=1;
void clear(){
	for(int i=1;i<=n+5;i++)head[i]=0;
	for(int i=1;i<=tot;i++)E[i]={0,0,0};
	tot=1;
	return;
}
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	head[u]=tot;
	return;
}
int a1,a2,an,b1,b2,bn,c,cnt;
char bri[51][51];
void conn(){
	for(int i=1;i<=c;i++){
		for(int j=i+1;j<=c;j++){
			if(bri[i][j]=='O')addE(i,j,1),addE(j,i,1);
			if(bri[i][j]=='N')addE(i,j,1e9),addE(j,i,1e9);
		}
	}
	return;
}
int dis[62505],cur[62505];
queue<int> q;
bool bfs(){
	for(int i=1;i<=t;i++)dis[i]=1e9;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=E[i].link){
			if(E[i].flow&&dis[E[i].to]>dis[u]+1){
				dis[E[i].to]=dis[u]+1;
				q.push(E[i].to);
			}
		}
	}
	return dis[t]!=1e9;
}
int dfs(int now,int maxflow){
	if(maxflow==0||now==t)return maxflow;
	int nowflow=0;
	for(int i=head[now];i;i=E[i].link){
		if(dis[E[i].to]==dis[now]+1){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				if(maxflow==nowflow)break;
			}
		}
	}
	return nowflow;
}
int dinic(){
	int res=0;
	while(bfs()){
		for(int i=1;i<=t;i++)cur[i]=head[i];
		res+=dfs(s,1e9);
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	while(cin>>c){
		cin>>a1>>a2>>an>>b1>>b2>>bn;
		a1++,a2++,b1++,b2++;
		n=c;
		s=n+1;
		t=s+1;
		for(int i=1;i<=c;i++){
			for(int j=1;j<=c;j++){
				cin>>bri[i][j];
			}
		}
		conn();
		addE(s,a1,an);
		addE(a1,s,0);
		addE(a2,t,an);
		addE(t,a2,0);
		addE(s,b1,bn);
		addE(b1,s,0);
		addE(b2,t,bn);
		addE(t,b2,0);
		int _=dinic();
		// cout<<_;
		clear();
		if(_!=an+bn){
			cout<<"No\n";
			continue;
		}
		conn();
		addE(s,a1,an);
		addE(a1,s,0);
		addE(a2,t,an);
		addE(t,a2,0);
		addE(s,b2,bn);
		addE(b2,s,0);
		addE(b1,t,bn);
		addE(t,b1,0);
		_=dinic();
		if(_!=an+bn)cout<<"No\n";
		else cout<<"Yes\n";
		clear();
	}
	return 0;
}

其余例题有待补充。

最小割

定义

对于一个图 G=(V,E)G=(V,E)，如果存在一个可行的割边方案，使原图被分成两个集合 a,ba,b，其中 S∈a,T∈bS\in a,T\in b，且 aa 集合与 bb 集合不连通，那么就称这个割边方案为 割。最小割的定义就是割边方案中所有割的边的容量之和最小的一种割边方式。

最小割最大流定理

就是最小割 = 最大流的一个定理，但是不会证，输！

据 yny 的 PPT，大概就是最小割限制了最大流的大小，而最大流又是一种可行的最小割，所以两者相等。

求最小割的方案

一种简单的分法是，再在残量网络从源点开始跑 bfs，能到的点分在集合 aa 中，不能分到的点分在集合 bb 中。

证明很简单，就是因为 a,ba,b 两个集合不联通。

例题

文理分科

这其实是一类题，这一类题都有套路。

这种题就是假如说选 AA 或选 BB 都有一些收益，而一些特定的集合如果全部选 AA 或者 BB 可以获得额外的一些收益。

我们使用最小割的思路，化收益为代价。具体就是假定我们先已经把所有的收益都拿到了，但是因为某些限制需要放弃一些收益，这样就变成了求最小代价。

然后把图画出来，尝试构造一种如果割掉某一种边那么就必须要割掉与之相关的某条边的建图方案。

对于文理分科这道题，对于每一个人先建一个点，源点向它连权值为文科收益的边，它向汇点连全职为理科收益的边，不难发现最大收益就是总收益减去最小割。

对于题中给的特殊条件，建立一个虚点 ii，ii 连向四周同学，SS 连 ii 权值为特殊的那个价值。对于汇点 TT 则是 ii 连向 TT。以源点连的特殊点为例，如果 S→S\to 四周同学的边有一条被割掉了，那么相应的 $S\to i\to $ 那个同学的边也应该被割掉，而 i→i\to 那个同学的边权为 +∞+\infty，割掉它一定不优，所以一定会删掉 S→iS\to i 的边，也就放弃了这个收益。

切糕

同样是非常经典的题。

把点当作边，如果割掉该边代表付出这个点的代价。

对于上下相邻的限制，我们的目的就是阻断它两割点之间的距离大于 DD。不难发现我们可以对于这种情况多连一条 k,a→k−1,a−Dk,a\to k-1,a-D 的权值为 +∞+\infty 的边，可以保证在割掉 k,a→k,a+1k,a\to k,a+1 这条边时能保证不会删掉 k−1,a−Dk-1,a-D 点之前的边。另一侧的连边方式相同。

其余例题有待添加。

最小割树

用来多次询问一张图中的两点之间的最小割。

思想

就是类似于整体二分的一种思想。

有一个神秘的结论，即 nn 个点的图中两两点对的本质不同最小割只有 n−1n-1 种。那么我们可以建一棵树来回答所有询问。而网络流题目通常点数较少，所以基本可以暴力做，不行就用倍增做也可以。

考虑首先对所有图任取两点做一遍最小割，然后找到两个割集，在树边上连接这两个点，边权为最小割的容量。对左右两个割集重新建边跑最小割，最后能跑出一棵树，然后不难发现树上两点之间的最小割就是路径上边的最小值。

板子题

P4897

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
// Problem: P4897 【模板】最小割树（Gomory-Hu Tree）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4897
// Memory Limit: 125 MB
// Time Limit: 500000 ms
// Start coding at 2023-12-11 16:24:58
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct line{
	int to,link,flow,tw;
}E[200001],T[200001];
int head[100001],headt[100001],tot=1,tott;
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	head[u]=tot;
	return;
}
void addT(int u,int v,int w){
	T[++tott].link=headt[u];
	T[tott].to=v;
	T[tott].tw=w;
	headt[u]=tott;
	return;
}
int p[200001],p1[200001],p2[200001];
void clear(){
	for(int i=1;i<=n;i++)head[i]=0;
	// for(int i=1;i<=tot;i++)E[i]={0,0,0,0};
	tot=1;
	return;
}
int dis[200001];
int x[100005],y[100005],z[100005];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=1e9;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=E[i].link){
			if(dis[E[i].to]>dis[u]+1&&E[i].flow){
				dis[E[i].to]=dis[u]+1;
				q.push(E[i].to);
			}
		}
	}
	return dis[t]!=1e9;
}
int cur[200001];
int dfs(int now,int maxflow){
	if(maxflow==0||now==t)return maxflow;
	int nowflow=0;
	for(int &i=cur[now];i;i=E[i].link){
		if(dis[E[i].to]==dis[now]+1){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				if(maxflow==nowflow)break;
			}
		}
	}
	return nowflow;
}
int dinic(){
	int res=0;
	while(bfs()){
		// cerr<<res<<"\n";
		for(int i=1;i<=n;i++)cur[i]=head[i];
		res+=dfs(s,1e9);
	}
	return res;
}
void conn(){
	clear();
	for(int i=1;i<=m;i++)addE(x[i],y[i],z[i]),addE(y[i],x[i],z[i]);
	return;
}
unordered_set<int> o;
void Count(int now){
	o.insert(now);
	// cerr<<now<<"\n";
	for(int i=head[now];i;i=E[i].link){
		// if(now==497)cerr<<i<<"\n";
		if(E[i].flow&&!o.count(E[i].to))Count(E[i].to);
	}
	return;
}
void solve(int l,int r){
	// cerr<<l<<" "<<r<<"\n";
	if(l==r)return;
	int cnt1=0,cnt2=0;
	s=p[l],t=p[r];
	conn();
	int _=dinic();
	// cerr<<head[0]<<" "<<E[1806].to<<" in\n";
	addT(s,t,_);
	addT(t,s,_);
	o.clear();
	Count(s);
	// cerr<<"in2\n";
	for(int i=l;i<=r;i++){
		if(o.count(p[i]))p1[++cnt1]=p[i];
		else p2[++cnt2]=p[i];
	}
	for(int i=1;i<=cnt1;i++)p[i+l-1]=p1[i];
	for(int i=1;i<=cnt2;i++)p[i+l+cnt1-1]=p2[i];
	solve(l,l+cnt1-1);
	solve(l+cnt1,l+cnt1+cnt2-1);
	return;
}
int lgn;
int dep[100005],siz[100005],fa[100005],ww[100005];
void dfs1(int now,int f){
	fa[now]=f;
	siz[now]=1;
	for(int i=headt[now];i;i=T[i].link){
		if(T[i].to==f)continue;
		dep[T[i].to]=dep[now]+1;
		ww[T[i].to]=T[i].tw;
		dfs1(T[i].to,now);
		siz[now]+=siz[T[i].to];
	}
	return;
}
int qu(int u,int v){
	int res=1e9;
	if(dep[u]>dep[v])swap(u,v);
	for(int i=dep[v]-dep[u];i;i--)res=min(res,ww[v]),v=fa[v];
	while(v!=u){
		res=min(res,ww[u]);
		res=min(res,ww[v]);
		u=fa[u];
		v=fa[v];
	}
	// if(res==1e9)return 0;
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	n++;
	lgn=log2(n);
	for(int i=1;i<=m;i++){
		cin>>x[i]>>y[i]>>z[i];
		x[i]++,y[i]++;
	}
	for(int i=1;i<=n;i++)p[i]=i;
	// s=1,t=2;
	// cout<<dinic()<<"\n";
	solve(1,n);
	// return 0;
	dfs1(1,0);
	int q,u,v;
	// return 0;
	cin>>q;
	while(q--){
		cin>>u>>v;
		u++;
		v++;
		cout<<qu(u,v)<<"\n";
	}
	return 0;
}

草泥马，zfy 跟我说没有编号为 00 的点，但是实际上是有的，虚空调试！c！

例题

P4123

建出最小割树，不难发现答案就是对树的边权离散化之后的结果。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Problem: P4123 [CQOI2016] 不同的最小割
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4123
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// Start coding at 2023-12-11 20:00:13
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
struct line{
	int to,link,flow,tw;
}E[200005],T[200005];
int head[100005],headt[100005],tot=1,tott;
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	head[u]=tot;
	return;
}
void addT(int u,int v,int w){
	T[++tott].link=headt[u];
	T[tott].to=v;
	T[tott].tw=w;
	headt[u]=tott;
	return;
}
int n,m,s,t;
void clear(){
	for(int i=1;i<=n;i++)head[i]=0;
	tot=1;
	return;
}
int x[100005],y[100005],z[100005];
void conn(){
	clear();
	for(int i=1;i<=m;i++)addE(x[i],y[i],z[i]),addE(y[i],x[i],z[i]);
	return;
}
int dis[100005];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=1e9;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		// cerr<<u<<"\n";
		for(int i=head[u];i;i=E[i].link){
			if(dis[E[i].to]>dis[u]+1&&E[i].flow){
				dis[E[i].to]=dis[u]+1;
				q.push(E[i].to);
			}
		}
	}
	return dis[t]!=1e9;
}
int cur[100005];
int dfs(int now,int maxflow){
	if(maxflow==0||now==t)return maxflow;
	int nowflow=0;
	for(int &i=cur[now];i;i=E[i].link){
		if(dis[E[i].to]==dis[now]+1){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				if(nowflow==maxflow)break;
			}
		}
	}
	return nowflow;
}
int dinic(){
	int res=0;
	while(bfs()){
		// cerr<<1<<"\n";
		for(int i=1;i<=n;i++)cur[i]=head[i];
		res+=dfs(s,1e9);
	}
	return res;
}
unordered_set<int> o;
void Count(int now){
	o.insert(now);
	for(int i=head[now];i;i=E[i].link){
		if(E[i].flow&&!o.count(E[i].to))Count(E[i].to);
	}
	return;
}
int p[100001],p1[100001],p2[100001];
void solve(int l,int r){
	// cerr<<l<<" "<<r<<"\n";
	if(l==r)return;
	int cnt1=0,cnt2=0;
	s=p[l],t=p[r];
	conn();
	int _=dinic();
	// cerr<<"in\n";
	o.clear();
	Count(s);
	addT(s,t,_);
	addT(t,s,_);
	for(int i=l;i<=r;i++){
		if(o.count(p[i]))p1[++cnt1]=p[i];
		else p2[++cnt2]=p[i];
	}
	for(int i=1;i<=cnt1;i++)p[i+l-1]=p1[i];
	for(int i=1;i<=cnt2;i++)p[i+l+cnt1-1]=p2[i];
	solve(l,l+cnt1-1);
	solve(l+cnt1,l+cnt1+cnt2-1);
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>x[i]>>y[i]>>z[i];
	for(int i=1;i<=n;i++)p[i]=i;
	solve(1,n);
	o.clear();
	for(int i=1;i<=tott;i++){
		o.insert(T[i].tw);
	}
	cout<<o.size();
	return 0;
}

感觉最小割树的题都是板子题，所以就不写了。

题：P3329，UVA11594，P4214。

最小割的一些经典模型

最大权闭合子图

定义

最大权闭合子图就是指求一个带点权的图的最大收益，但是点权可能为负，并且要保证如果选了节点 uu，那么 uu 指向的所有节点都要被选。

这类型的题使用最小割来解决。首先，我们假设我们选了所有正点权的点并不选所有负点权的点。显然这样选是保证点权最大的。然后建出原来的图，每条边容量均为 +∞+\infty，对于正点权的点，由 SS 连向它，表示放弃该点的收益；对于负点权的点，将它连向 TT，表示选择该点，容量为点权的绝对值。

例题：P4177 [CEOI2008] order

考虑工作与机器有依赖关系，那么就可以使用最大权闭合子图的思路来做。SS 连向工作，容量为工作收益，割掉此边代表放弃该工作的收益。机器连向 TT，容量为购买的代价，割掉此边代表购买该机器。每个工作连向完成该工作需要的机器，权值为 +∞+\infty。这是没有租用操作的做法。

但是此时多出了一个租用的操作。怎么办呢？考虑原来工作连向机器的 +∞+\infty 的本质。这条边代表这台机器是完成该工作的前提。换个思路理解一下，即该工作需要使用这台机器一次，正好匹配 租用机器能使用机器一次 的题意，这样机器连向汇点的边即表示这台机器被无限使用时的代价。那么综上所述，针对于租用机器，我们把每一个机器被连向的边的容量设为租用该机器所需要的代价，割掉这条边代表租用该机器进行一个工作。

代码就不贴了。

其他例题待补。

上下界网络流

上下界循环流

即指无源汇上下界可行流。

考虑由于有下界限制，为了转化成最大流，干脆就当作每条边已经流了下界的流量了。这个时候会造成某些点的流量不平衡，即流入量不等于流出量。此时考虑把这些流量不平衡全部转化成源点和汇点的流量不平衡。设 kk 为流入量，mm 为流出量，有以下 33 种可能出现的情况：

  • k=mk=m，此时流量平衡，不需要进行任何操作。
  • k>mk>m，此时流入量偏多，那么就把多出来的流入量当作是虚拟源点流过来的（即不是原图的流量），即建出虚拟源点 S′S'，连向该点，容量为 k−mk-m。
  • k<mk<m，此时流出量偏多，那么就把多出来的流出量当作是流向虚拟汇点的（当作为非原图的流量），即建出虚拟汇点 T′T'，该点连向虚拟汇点，容量为 m−km-k。

对于原图上的边，我们要规约虚拟边的流量，即对于原图的每一条边，复制一条容量为其上界减下界的一条边。

对于新建出来的图跑最大流，如果从 S′S' 连出的边都满流了，那么有可行解。

有源汇上下界可行流

考虑汇点向源点连一条上界为 +∞+\infty ，下界为 00 的边，问题被转化成上下界循环流。

如果要求可行流的流量，那么就直接取从 TT 到 SS 的新连的 +∞+\infty 边的反向边流量即可。

有源汇上下界最大流

考虑首先跑一遍有源汇上下界可行流，然后不难发现可行流有上下浮动的空间，那么直接在可行流的残量网络中以原图的源点和汇点跑一遍最大流，两者相加即可。

注意，在跑残量网络的最大流之前要把原来连的 TT 到 SS 的边的容量设成 00。

有源汇上下界最小流

这个我不会证明。

和最大流相似，但是只不过是把最后一次的最大流源点和汇点交换一下。

例题

P5192

板子题，建模思路平凡。

比较容易写挂，注意清空和对于初始流的统计。初始流的统计要算上建出来的原图上的源点和汇点。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// Problem: P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5192
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-12 18:46:58
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct line{
	int to,link,flow,up,down,from;
}E[2000001];
int head[1000001],tot=1;
int n,m,s,t;
int in[1000001],out[1000001];
void clear(){
	for(int i=1;i<=n;i++)head[i]=0;//,in[i]=0,out[i]=0;
	// for(int i=1;i<=tot;i++)E[i]={0,0,0,0,0,0};
	tot=1;
	return;
}
void addE(int u,int v,int w1,int w2){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].down=w1;
	E[tot].up=w2;
	E[tot].from=u;
	head[u]=tot;
	return;
}
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	head[u]=tot;
	return;
}
int dis[1000001];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=1e9;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=E[i].link){
			if(dis[E[i].to]>dis[u]+1&&E[i].flow){
				dis[E[i].to]=dis[u]+1;
				q.push(E[i].to);
			}
		}
	}
	return dis[t]!=1e9;
}
int cur[1000001];
int dfs(int now,int maxflow){
	if(maxflow==0||now==t)return maxflow;
	int nowflow=0;
	for(int &i=cur[now];i;i=E[i].link){
		if(dis[E[i].to]==dis[now]+1){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				if(maxflow==nowflow)break;
			}
		}
	}
	return nowflow;
}
int dinic(){
	int res=0;
	while(bfs()){
		for(int i=1;i<=n;i++)cur[i]=head[i];
		res+=dfs(s,1e9);
	}
	return res;
}
int nn,mm;
int xx[1000001],yy[1000001],zz[1000001];
signed main(){
	ios::sync_with_stdio(0);
	while(cin>>nn>>mm){
		int cc=0;
		n=nn+mm+4;
		int ss=n-1,tt=n;
		int _s=n-3,_t=n-2;
		// clear();
		int op,oo;
		for(int i=1;i<=mm;i++){
			cin>>op;
			addE(i+nn,tt,op,1e9);
			// out[i+nn]=op;
		}
		int x,y,z;
		for(int i=1;i<=nn;i++){
			cin>>op>>oo;
			addE(ss,i,0,oo);
			for(int j=1;j<=op;j++){
				cin>>x>>y>>z;
				addE(i,x+nn+1,y,z);
			}
		}
		for(int i=1;i<=tot;i++){
			in[E[i].to]+=E[i].down;
			out[E[i].from]+=E[i].down;
			xx[++cc]=E[i].from;
			yy[cc]=E[i].to;
			zz[cc]=E[i].up-E[i].down;
		}
		clear();
		int sum=0;
		for(int i=1;i<=n;i++){
			if(in[i]>out[i])addE(_s,i,in[i]-out[i]),addE(i,_s,0),sum+=in[i]-out[i];
			else if(in[i]<out[i])addE(i,_t,out[i]-in[i]),addE(_t,i,0);
			// in[i]=0,out[i]=0;
		}
		for(int i=1;i<=cc;i++){
			addE(xx[i],yy[i],zz[i]);
			addE(yy[i],xx[i],0);
		}
		s=_s,t=_t;
		addE(tt,ss,1e9);
		addE(ss,tt,0);
		int _=dinic();
		// cerr<<_<<" "<<sum<<"\n";
		if(_!=sum){
			cout<<"-1\n\n";
			clear();
			for(int i=1;i<=n;i++)in[i]=out[i]=0;
			continue;
		}
		int ans=E[tot].flow;//+out[ss];
		// cout<<out[ss];
		E[tot].flow=0;
		E[tot-1].flow=0;
		s=ss,t=tt;
		ans+=dinic();
		cout<<ans<<"\n\n";
		clear();
		for(int i=1;i<=n;i++)in[i]=out[i]=0;
	}
	return 0;
}

只能说写的非常丑。

P4043

最小费用可行流。

不难发现我们要把每一条边都走一遍，那么每条边的流量为 [1,+∞][1,+\infty]，源点为 11 号剧情点，将每个剧情的结束点（出度为 00）连向 TT，容量为 [0,∞][0,\infty]。

同样的，我们把入流和出流不同的点进行处理，跑一遍最小费用最大流，然后再进行费用的加减，即加上所有边的下界流量乘上该边费用即可。

说实话，这种题就该图图了，为什么让选手写这么长代码？？？/fn/fn/fn

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
// Problem: P4043 [AHOI2014/JSOI2014] 支线剧情
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4043
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-13 15:48:40
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
struct line{
	int to,link,up,down,flow,money,from;
}E[2000005];
int head[2000005],tot=1;
void clear(){
	for(int i=1;i<=n;i++)head[i]=0;
	tot=1;
	return;
}
void addE(int u,int v,int w1,int w2,int mon){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].from=u;
	E[tot].down=w1;
	E[tot].up=w2;
	E[tot].money=mon;
	head[u]=tot;
	return;
}
void addE(int u,int v,int w,int mon){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	E[tot].money=mon;
	head[u]=tot;
	return;
}
// int deg[1000001];
int dis[1000001],vis[1000001];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=1e18,vis[i]=0;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=E[i].link){
			if(dis[E[i].to]>dis[u]+E[i].money&&E[i].flow){
				dis[E[i].to]=dis[u]+E[i].money;
				if(!vis[E[i].to]){
					q.push(E[i].to);
					vis[E[i].to]=1;
				}
			}
		}
	}
	return dis[t]!=1e18;
}
int cur[1000001];
int resmon;
int dfs(int now,int maxflow){
	if(now==t||maxflow==0)return maxflow;
	vis[now]=1;
	int nowflow=0;
	for(int &i=cur[now];i;i=E[i].link){
		if(!vis[E[i].to]&&dis[E[i].to]==dis[now]+E[i].money){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				resmon+=flow*E[i].money;
				if(maxflow==nowflow)break;
			}
		}
	}
	vis[now]=0;
	return nowflow;
}
int dinic(){
	int res=0;
	resmon=0;
	while(bfs()){
		for(int i=1;i<=n;i++)cur[i]=head[i],vis[i]=0;
		res+=dfs(s,1e9);
	}
	return res;
}
int in[1000001],out[1000001];
int x[1000001],y[1000001],xx[1000001],yy[1000001];
signed main(){
	ios::sync_with_stdio(0);
	int nn;
	cin>>nn;
	n=nn+3;
	int ss=1,tt=nn+1;
	int _s=nn+2,_t=nn+3;
	int o1,o2,oo;
	for(int i=1;i<=nn;i++){
		cin>>oo;
		for(int j=1;j<=oo;j++){
			cin>>o1>>o2;
			x[++m]=i;
			y[m]=o1;
			xx[m]=1e9-1;
			yy[m]=o2;
			addE(i,o1,1,1e9,o2);
		}
		if(i!=1){
			addE(i,tt,0,1e9,0);
			x[++m]=i;
			y[m]=tt;
			xx[m]=1e9;
			yy[m]=0;
		}
	}
	int ans=0;
	for(int i=1;i<=tot;i++){
		in[E[i].to]+=E[i].down;
		out[E[i].from]+=E[i].down;
		ans+=E[i].down*E[i].money;
	}
	clear();
	for(int i=1;i<=m;i++){
		addE(x[i],y[i],xx[i],yy[i]);
		addE(y[i],x[i],0,-yy[i]);
	}
	for(int i=1;i<=nn+1;i++){
		if(in[i]>out[i])addE(_s,i,in[i]-out[i],0),addE(i,_s,0,0);
		else if(in[i]<out[i])addE(i,_t,out[i]-in[i],0),addE(_t,i,0,0);
	}
	addE(tt,ss,1e9,0);
	addE(ss,tt,0,0);
	s=_s,t=_t;
	dinic();
	ans+=resmon;
	cout<<ans;
	return 0;
}

最小费用最大流

就是把 bfs 换成 spfa 或 Johnson。

Johnson 已经忘了，通常是 spfa 时间的一半，但是没有人会卡这个。

建边时注意反向边费用为正向边相反数，流量为 00。

例题

P2053 修车

考虑把每个师傅师傅拆成 nn 个点，代表这个师傅在修第 kk 辆车。考虑修第 kk 辆车对于答案的贡献是 wk×kw_k\times k（可以模拟答案产生过程来理解）。那么直接跑带权二分图匹配即可。

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
// Problem: P2053 [SCOI2007] 修车
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2053
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-14 10:57:02
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct line{
	int to,link,flow,money;
}E[200001];
int head[100001],tot=1;
void addE(int u,int v,int w,int mon){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	E[tot].money=mon;
	head[u]=tot;
	return;
}
int dis[100001],vis[100001];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=1e9,vis[i]=0;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=E[i].link){
			if(dis[E[i].to]>dis[u]+E[i].money&&E[i].flow){
				dis[E[i].to]=dis[u]+E[i].money;
				if(!vis[E[i].to]){
					q.push(E[i].to);
					vis[E[i].to]=1;
				}
			}
		}
	}
	return dis[t]!=1e9;
}
int resmon=0;
int cur[100001];
int dfs(int now,int maxflow){
	if(now==t||maxflow==0)return maxflow;
	int nowflow=0;
	vis[now]=1;
	for(int &i=cur[now];i;i=E[i].link){
		if(!vis[E[i].to]&&dis[E[i].to]==dis[now]+E[i].money){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				resmon+=flow*E[i].money;
				if(maxflow==nowflow)break;
			}
		}
	}
	vis[now]=0;
	return nowflow;
}
int dinic(){
	int res=0;
	resmon=0;
	while(bfs()){
		// cerr<<1<<"\n";
		for(int i=1;i<=n;i++)cur[i]=head[i],vis[i]=0;
		res+=dfs(s,1e9);
	}
	return res;
}
int fy[61][61];
int as[61][61];
int main(){
	ios::sync_with_stdio(0);
	int nn,mm;
	cin>>mm>>nn;
	int ucnt=nn+1;
	for(int i=1;i<=mm;i++){
		for(int j=1;j<=nn;j++){
			as[i][j]=++ucnt;
		}
	}
	s=1+ucnt;
	t=s+1;
	for(int i=1;i<=nn;i++)addE(s,i,1,0),addE(i,s,0,0);
	for(int i=nn+1;i<=ucnt;i++)addE(i,t,1,0),addE(t,i,0,0);
	for(int i=1;i<=nn;i++){
		for(int j=1;j<=mm;j++){
			cin>>fy[i][j];
			for(int k=1;k<=nn;k++){
				addE(i,as[j][k],1,fy[i][j]*k);
				addE(as[j][k],i,0,-fy[i][j]*k);
			}
		}
	}
	n=t+1;
	dinic();
	cout<<fixed<<setprecision(2)<<1.0*resmon/nn;
	return 0;
}

P3705 新生舞会

考虑二分答案 CC，不难发现有以下关系：

a1−b1C+a2−b2C+a3−b3C+⋯=0a_1-b_1C+a_2-b_2C+a_3-b_3C+\cdots=0

由于要求出 CC 的最大值，不难发现随着 CC 的升高，原来这个式子的最大值也在降低，我们正要求出这个式子最大值为 00 时 CC 的值。

使用最大费用最大流计算连出的二分图，对于左边的点 ii 和右边的点 jj 连一条费用为 ai,j−C×bi,ja_{i,j}-C\times b_{i,j} 的边，跑出的费用即为上面那个式子的最大值。

如果这个最大值小于 00，那么此时 CC 是取不到的，而这个最大值大于 00，那么 CC 值可以继续增加。

跑 log⁡V\log V 次费用流即可。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// Problem: P3705 [SDOI2017] 新生舞会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3705
// Memory Limit: 250 MB
// Time Limit: 1500 ms
// Start coding at 2023-12-14 15:15:02
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
struct line{
	int to,link,flow;
	double money;
}E[200005];
int head[100005],tot=1;
int n,m,s,t;
void clear(){
	for(int i=1;i<=n;i++)head[i]=0;
	tot=1;
}
void addE(int u,int v,int w,double mon){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	E[tot].money=mon;
	head[u]=tot;
	return;
}
double dis[100001];
int vis[100001];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=-2e9;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=E[i].link){
			if(E[i].flow&&dis[E[i].to]<dis[u]+E[i].money){
				dis[E[i].to]=dis[u]+E[i].money;
				if(!vis[E[i].to]){
					vis[E[i].to]=1;
					q.push(E[i].to);
				}
			}
		}
	}
	// cerr<<dis[t]<<" ?\n";
	return dis[t]!=-2e9;
}
int cur[100001];
double resmon;
int dfs(int now,int maxflow){
	if(now==t||maxflow==0)return maxflow;
	int nowflow=0;
	vis[now]=1;
	for(int &i=cur[now];i;i=E[i].link){
		if(!vis[E[i].to]&&dis[E[i].to]==dis[now]+E[i].money){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				resmon+=flow*E[i].money;
				if(nowflow==maxflow)break;
			}
		}
	}
	vis[now]=0;
	return nowflow;
}
int dinic(){
	int res=0;
	resmon=0;
	while(bfs()){
		// cerr<<1;
		for(int i=1;i<=n;i++)cur[i]=head[i],vis[i]=0;
		res+=dfs(s,2e9);
	}
	return res;
}
int nn;
int a[101][101],b[101][101];
void conn(double num){
	clear();
	for(int i=1;i<=nn;i++){
		for(int j=1;j<=nn;j++){
			addE(i,j+nn,1,0.0+a[i][j]-num*b[i][j]);
			addE(j+nn,i,0,0.0+num*b[i][j]-a[i][j]);
		}
	}
	for(int i=1;i<=nn;i++){
		addE(s,i,1,0);
		addE(i,s,0,0);
		addE(i+nn,t,1,0);
		addE(t,i+nn,0,0);
	}
	return;
}
bool check(double C){
	conn(C);
	dinic();
	// cerr<<resmon<<"\n";
	return resmon>=0;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>nn;
	for(int i=1;i<=nn;i++){
		for(int j=1;j<=nn;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=nn;i++){
		for(int j=1;j<=nn;j++){
			cin>>b[i][j];
		}
	}
	n=nn*2+2;
	s=n-1,t=n;
	double l=0,r=1e6;
	while(r-l>1e-7){
		double mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<fixed<<setprecision(6)<<l<<"\n";
	return 0;
}

P3980 志愿者招募

这道题需要对循环流有很深的理解。

考虑使用上下界费用流来做（因为没看懂正经费用流做法）。不难发现最朴素的建图就是建一条 i→i+1i\to i+1，容量为 [ai,+∞][a_i,+\infty]，由于很难用有源汇的网络流来付费，考虑使用循环流。我们连一个 ti+1→sit_i+1\to s_i 的边，容量为 +∞+\infty，费用为 cic_i。

不难发现此时已经有一个循环流了，那么我们只需要跑一遍上下界最小费用循环流即可。

这里需要注意一下，最小费用循环流正经做法求出来的本来就是最小费用，如果要加上什么最大流或最小流，就不能保证最小费用。

尼玛请别出上下界网络流了谢谢。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// Problem: P3980 [NOI2008] 志愿者招募
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3980
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// Start coding at 2023-12-14 16:55:14
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int I=1e14;
struct line{
	int to,link,from,up,down,flow,money;
}E[200005];
int head[100005],tot=1;
void addE(int u,int v,int w1,int w2,int mon){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].from=u;
	E[tot].down=w1;
	E[tot].up=w2;
	E[tot].money=mon;
	head[u]=tot;
	return;
}
void addE(int u,int v,int w,int mon){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].flow=w;
	E[tot].money=mon;
	head[u]=tot;
	return;
}
int n,m,s,t;
void clear(){
	for(int i=1;i<=n;i++)head[i]=0;
	tot=1;
	return;
}
int dis[100001],vis[100001];
queue<int> q;
bool bfs(){
	for(int i=1;i<=n;i++)dis[i]=I;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=E[i].link){
			if(E[i].flow&&dis[E[i].to]>dis[u]+E[i].money){
				dis[E[i].to]=dis[u]+E[i].money;
				if(!vis[E[i].to]){
					vis[E[i].to]=1;
					q.push(E[i].to);
				}
			}
		}
	}
	return dis[t]!=I;
}
int resmon;
int cur[100001];
int dfs(int now,int maxflow){
	if(now==t||maxflow==0)return maxflow;
	int nowflow=0;
	vis[now]=1;
	for(int i=head[now];i;i=E[i].link){
		if(!vis[E[i].to]&&dis[E[i].to]==dis[now]+E[i].money){
			int flow=dfs(E[i].to,min(maxflow-nowflow,E[i].flow));
			if(flow){
				E[i].flow-=flow;
				E[i^1].flow+=flow;
				nowflow+=flow;
				resmon+=flow*E[i].money;
				if(maxflow==nowflow)break;
			}
		}
	}
	vis[now]=0;
	return nowflow;
}
int dinic(){
	int res=0;
	resmon=0;
	while(bfs()){
		// cerr<<1<<"\n";
		for(int i=1;i<=n;i++)cur[i]=head[i],vis[i]=0;
		res+=dfs(s,I);
	}
	return res;
}
int in[100001],out[100001];
int nn,mm;
int xx[100001],yy[100001],xxx[100001],yyy[1000001];
signed main(){
	ios::sync_with_stdio(0);
	cin>>nn>>mm;
	n=nn+3;
	s=n-1,t=n;
	int x,y,z;
	for(int i=1;i<=nn;i++){
		cin>>x;
		addE(i,i+1,x,I,0);
		xx[++m]=i;
		yy[m]=i+1;
		xxx[m]=I-x;
		yyy[m]=0;
	}
	for(int i=1;i<=mm;i++){
		cin>>x>>y>>z;
		addE(y+1,x,0,I,z);
		xx[++m]=y+1;
		yy[m]=x;
		xxx[m]=I;
		yyy[m]=z;
	}
	for(int i=1;i<=tot;i++){
		in[E[i].to]+=E[i].down;
		out[E[i].from]+=E[i].down;
		resmon+=E[i].down*E[i].money;
	}
	clear();
	for(int i=1;i<=m;i++){
		addE(xx[i],yy[i],xxx[i],yyy[i]);
		addE(yy[i],xx[i],0,-yyy[i]);
	}
	for(int i=1;i<=nn+1;i++){
		if(in[i]>out[i])addE(s,i,in[i]-out[i],0),addE(i,s,0,0);
		else if(in[i]<out[i])addE(i,t,out[i]-in[i],0),addE(t,i,0,0);
	}
	dinic();
	// cout<<dinic()<<"\n";
	cout<<resmon;
	return 0;
}

其他例题待补。

模拟费用流

鸽…