网络流

概念：

• 一个边有两个权值且带有汇点与源点的无向图 $G(V,E)$，其中每条边为 $x,y,c,w$ 四个参数组成，$x,y$ 表示起始点和结束点，$c$ 表示最大容量，$w$ 表示单位时间通过容量。

性质：

• 对于任意一条边 $x,y,c,w$，满足 $w \le c$。
• 对于任意一条边 $x,y,c,w$，满足存在另一条边 $y,x,0,-w$。
  • 后面这条边可能题目没有给出，需要自己加上去。
• 设 $in_x = \sum_{y \to x}w$，$out_x = \sum_{x \to y}w$，若 $x$ 不为汇点和源点，那么 $in_x=out_x$。
• 设源点为 $s$，汇点为 $t$，则 $out_s=in_t$。

上面的性质分别称作：容量限制，斜对称性和流守恒性。

最大流

构造一个网络，使得 $out_s=in_t$ 最大，这个最大的值称作这个网络图的最大流。

显然，开始时这个图的最大流是 $0$，每条边的流量均为 $0$。

考虑找到一条从 $s \sim t$ 的路径，这条路径上的 $c-w$ 的最小值 $>0$，那么我们可以使全局的最大流加上这个最小值。

证明显然，只需要对应的边减一下，然后斜对称的边加一下就行了，因为有斜对称这个性质，所以相当于给了程序一个“反悔”的机会，可以把之前给各个边的流量减少一部分以扩充全局的流量。

只到最后图中不存在这条增广路即可。

EK 算法

每次暴力枚举可能的增广路，最多增广 $O(nm)$ 次，则时间复杂度为 $O(nm^2)$。

记得使用广度优先搜索。

Dinic

找增广路的过程中把所有 $c-w$ 非 $0$ 的边拿出来 01 BFS 一下，那么每个节点只去寻找 $dis_y=dis_x+1$ 的节点更新增广路，那么时间复杂度为 $O(n^2m)$。

注意 $dis_x$ 表示 $x$ 在 01 BFS 的图上与 $s$ 的最短路的长度，这样做一定是正确的，因为总是可以找到一条合法的路径。

ISAP

优化 Dinic 的过程，把 $dis_x$ 的定义换为在 01 BFS 的图上与 $t$ 的最短路的长度。

然后如果没有某个 $dis_x=i(1 \le i \le n-1)$，那么图出现了断层，此时返回即可。

而且我们可以一边找增广路一边更新 $dis$ 数组，不用每次 BFS 一遍，常数也比较小，代码如下所示：

（这里使用了当前弧优化，对于每一次更新我们经过的边就不会再选了，用链式前向星或者 vector 都可以）

通常没有 Dinic 快，请谨慎使用。

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

#include<bits/stdc++.h>
#define ll long long
#define N 500005
using namespace std;
ll n,m,s,t,i,x,y,z,ans,temp;
ll la[N],ne[N],to[N],val[N],dis[N],cur[N],tot=1,sum[N];
inline void merge(ll x,ll y,ll z){tot++,ne[tot] = la[x],la[x] = tot,to[tot] = y,val[tot] = z;}
ll dfs(ll x,ll step){
	if(x==t) return step;
	ll used = 0;
	for(ll i=cur[x];i;i=ne[i]){
		cur[x] = i;
		if(dis[to[i]]+1==dis[x]&&val[i]>0){
			ll temp = dfs(to[i],min(val[i],step-used));
			val[i] -= temp,val[i^1] += temp,used += temp;
			if(used==step) return used;
		}
	}
	if(--sum[dis[x]]==0) dis[s] = n+1;
	sum[++dis[x]]++;
	return used;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>s>>t;
	sum[0] = n;
	for(i=1;i<=m;i++){
		cin>>x>>y>>z;
		merge(x,y,z),merge(y,x,0);
	}
	while(dis[s]<n) memcpy(cur,la,sizeof(la)),ans+=dfs(s,1e18);
	cout<<ans<<endl;
	return 0;
} 

最小割

有一个定理，最大流 $=$ 最小割，详见算法导论。

最小割用于处理下列内容的最优解：

对于一张图，把图的两个点 $s,t$ 变得不连通，至少需要割掉边权总和为多少的边。

对于一些关系，如果 $a_i$ 号点划分到 $1$ 集合有 $c_i$ 的贡献，划分到 $2$ 集合有 $d_i$ 的贡献，并且有 $q$ 对关系，表示若 $u_i$ 和 $v_i$ 不在一个集合内，有 $-w_i$ 的贡献，最大化贡献。（数据都是非负整数）那么可以以此建立网络流模型。

大概处理的多数情况是第一种，第一种运用也很广泛，我们可以看一下下面这道例题：

有 $n \times m$ 的矩阵，每个格子可以选择 A、B 两类，如果一个格子选择 A 类，它的贡献是 $a_{i,j}$，否则贡献是 $b_{i,j}$。并且如果有 $k$ 个格子与它相邻并且类型不一样，获得 $k \times c_{i,j}$ 的收益，问收益最大是多少。

数据保证点数为 $n \times m$ 的 ISAP 能过。

显然的，这个矩阵是一个二分图，为了转化为最小割模型，考虑下面的操作。

1. $ans \gets \sum a_{i,j}+\sum b_{i,j}+\sum c_{i,j} \times ([i>1]+[j>1]+[i<n]+[j<m])$

   注解：这是所有的权值总和。

2. 连边 $s \to (i,j),w=b_{i,j}$，$(i,j) \to t,w=a_{i,j}$，这是二分图左部的点；连边 $s \to (i,j),w=a_{i,j}$，$(i,j) \to t,w=b_{i,j}$，这是二分图右部的点；然后若两个点相邻，设左部点为 $u$，右部点为 $v$，则连接 $u \to v,w=c_{u}+c_{v}$ 和 $v \to u,w=c_v+c_u$

   注解：如果把二分图左部的点划分到 $s$ 集合，那么 $(i,j) \to t$ 的边就会切断，减去 $a_{i,j}$，其余情况同理。如果左右部的点都划分到 A 类，那么左部的点就会划分到 $t$ 集合，右部的点就会划分到 $s$ 集合，如果它们其中有连边，那么这条边根据最小割的定义必须断开，然后就会减去之前加上的多余的 $sum$。

3. 输出之前的 $sum$ 减去最小割即可，满足答案最大。

注意：此处连双向边（$u \to v$ 和 $v \to u$）是因为每个点都与 $s$ 和 $t$ 有连边，根据题目也是如此，有些情况是只连单向边，需要特别注意一下。

还有一种题目：

对于一个有向图，找到点权总和最大的子图，使得这个子图中的点的所有出点都在这个子图中，点权可能为负。（最大闭合子图）

源点向点权为正的点连边，边权即为点权；图上如果有 $u \to v$ 的边，那么连接 $u \to v$，边权为 $\text{inf}$；点权为负的点向汇点连边，边权为点权的绝对值，跑最大流等于最小割即可。（点权为 $0$ 的其实不影响，可以算到点权为正的点集里面）

答案要减去最小割，然后加上点权为正的点的点权之和。

如果割掉源点到某个点的边，那么代表不选这个点，答案减去点权；如果割掉某个点到汇点的边，那么代表选这个点，答案减去点权的绝对值等于答案加上点权。

这样做显然是正确的，可以思考一下。

常见建图

这个，靠积累了，网络流 24 题和 Atcoder 的题目都可以积累。

最小割树

【模板】最小割树（Gomory-Hu Tree） 题解

费用流

我们对于每条边，如果流经它的流量为 $x$，那么答案增加 $cx$，$c$ 为这条边的边权。

然后前提要求是最大流。

最小费用最大流

把寻找增广路的过程用 spfa 找最小费用的某条增广路就可以了。

最后一定是最大流并且费用是最小的。

优化：每次增广的时候找最小费用的值，然后找增广路的时候多路增广即可，详见代码。

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

bool spfa(){
	for(ll i=0;i<inf;i++) dis[i]=0x3f3f3f3f3f3f3f3f;
	q.push(s);
	dis[s]=0;
	while(q.size()){
		ll tmp = q.front();
		q.pop();
		vis[tmp] = 0;
		for(ll i=la[tmp];i;i=ne[i]){
			if(val[i]>0&&dis[to[i]]>dis[tmp]+w[i]){
				dis[to[i]] = dis[tmp]+w[i];
				if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
			}
		}
	}
	return dis[t]<=1e18;
}
ll dfs(ll x,ll step){
	if(x==t) return step;
	viss[x] = 1;
	ll used = 0;
	for(ll i=la[x];i;i=ne[i]){
		if(dis[x]+w[i]==dis[to[i]]&&val[i]>0&&!viss[to[i]]){
			ll temp = dfs(to[i],min(val[i],step-used));
			val[i] -= temp,val[i^1] += temp,used += temp;
			if(used==step) return used;
		}
	}
	return used;
}

最大费用最大流

用 spfa 找最大费用的一条路就可以了，其余同上。

注：若初始的时候有未满流的边构成的正/负环，那么后面就可能会出现环，否则一定不会出现 spfa 死循环的情况，如果出现，请检查板子是否敲错！

建模

精简为一句话：往往是通过最大流来限制题目中要求的个数，然后用费用来表示在达到这个个数的时候费用最小/最大。

或者是最大流越大费用就会越小/越大，那么这个时候费用的作用就是用来保证个数一定恒为多少（赋值一个很大/小的数就可以了），然后还能顺便得知最小/最大费用。

性质

每次增广出来的路径权值总和一定是单调的，即 $dis_t$​ 单调递增或者递减。

Dijkstra 版本费用流

我们知道，费用流的使用依赖于 SPFA，对于一些特殊的图（最大流很小）则需要用复杂度更加稳定的 Dijkstra 解决。

首先如果我们在每次跑 SPFA 之前得到了从源点到各个点的最短路长 $dis_i$，那么把边权设为 $dis_i+w_{i,j}-dis_j$ 继续跑单源最短路之后，最短路和原图的最短路是相同的，这样的话因为 $dis_i+w_{i,j} \ge dis_j$，所以边权非负，直接用 Dijkstra 即可。

但是费用流的过程可能需要跑多次 SPFA，每次跑的时候我们都得知道 $dis$，才能使用 Dijkstra 解决，知道 $dis$ 又必须 SPFA，我们考虑去掉新跑 SPFA 的环节，只在最开始跑费用流之前就跑 SPFA 一遍知道 $dis$。

假设原来的 $dis$ 是 $h$，那么跑了一遍费用流之后，有一些边会被从图中删除，一些边会添加进图中，被删除的边一定满足 $dis_i+(h_i+w_{i,j}-h_j)=dis_j$，移项得 $w_{j,i}+(h_j+dis_j)-(h_i+dis_i)=0$，（反向边会被添加进去）边权为 $0$。

原本就在图上的边则 $dis_i+(h_i+w_{i,j}-h_j)\ge dis_j$，移项得 $w_{i,j}+(h_i+dis_i)-(h_j+dis_j)\ge 0$，边权大于 $0$，所以这个时候，如果令边权为 $w_{i,j}+(h_i+dis_i)-(h_j+dis_j)$，满足边权大于等于 $0$，可以直接用 Dijkstra 做，设跑出来的最短路为 $dis2$，那么 $h_i \gets h_i+dis2_i$ 即可。（之前 $h_i \gets h_i+dis_i$）

于是算法流程就是：

• 最开始跑 SPFA 最短路，得到最短路数组 $h$。
• 每次费用流之前令 $nw_{i,j}=w_{i,j}+h_i-h_j$，然后让 $nw$ 数组去跑 Dijkstra 最短路，设最短路数组为 $dis$，那么 $h_i \gets h_i+dis_i$。
• 然后 dfs 增广的时候用 $nw$ 和 $dis$ 数组判断两个点在不在同一层即可。
• 最后用 $h$ 数组更新最大/小费用。

考虑这么做的正确性，似乎只需要证明每次 $h$ 都是真实的最短路就可以了，这个还算比较显然，因为每次跑完增广路之后有一些边会被删除，设新的 $h$ 为 $h2$，那么 $dis_i$ 就是 $h2_i-h_i$，$dis$ 数组就是 $h$ 数组的增量，跑最短路的时候每一条边的增量都是 $w_{i,j}+h_i-h_j$，意味着换了一条最短路，所以答案是对的。

综上，一次最短路时间复杂度就被优化成了严格 $O(\log)$，但是其实大部分时间没有 SPFA 快。

上下界网络流

无源汇上下界网络可行流

定义

有一个 $n$ 个点 $m$ 条边的无向图，没有源点和汇点。

对于每一条边都设置一个流量 $c$ 使得 $l \le c \le r$ 且对于每个点都要满足流量守恒。（$l$ 和 $r$ 是这条边的上下界）

这样的一组方案称为无源汇上下界网络可行流。

解决

注意到有至少流 $l$ 个单位的限制，我们考虑去掉这个限制，首先一条边可以拆分成 $u \to v$ 容量为 $l$ 的边和 $u \to v$ 容量为 $r-l$ 的边。

其中容量为 $l$ 的边必须满流，容量为 $r-l$ 的边不能超流。

我们就可以考虑新建一个源点和汇点 $S$ 和 $T$，那么让 $S$ 向 $v$ 连接一条容量为 $l$ 的边，$u$ 向 $T$ 连接一条容量为 $l$ 的边，最后判断是否满流即可。（原图上的边只考虑 $r-l$ 的边，其余容量为 $l$ 的边不管就可以了）

考虑这个方法的正确性：

如果整张图满流，我们可以将从 $S$ 到 $v$ 的边和 $u$ 到 $T$ 的边删去，然后因为 $v$ 到 $u$ 有多出来的 $l$ 的流量，我们就可以让 $u$ 流到 $v$ 点 $l$ 的流量，并且满足流量守恒，可以证明这是充要条件。（如果这 $l$ 的流量用了其它边 $l’$ 的流量，那么因为其它边也像这样连接了源点和汇点，所以可以相互转移）

于是这道题就做完了，输出方案就是遍历每条边，检查当前消耗的流量数量加上 $l$ 即可。

代码如下，网络流使用 ISAP 实现。

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

#include<bits/stdc++.h>
#define ll long long
#define N 500005
using namespace std;
ll n,m,s,t,inf,i,j,x,y,l,r,z,ans,temp;
ll la[N],ne[N],to[N],val[N],dis[N],cur[N],id[N],tot=1,sum[N],anss[N];
inline void merge(ll x,ll y,ll z,ll ID){
	tot++,ne[tot] = la[x],la[x] = tot,to[tot] = y,val[tot] = z,id[tot] = ID;
	tot++,ne[tot] = la[y],la[y] = tot,to[tot] = x,val[tot] = 0,id[tot] = -1;
}
ll dfs(ll x,ll step){
	if(x==t) return step;
	ll used = 0;
	for(ll i=cur[x];i;i=ne[i]){
		cur[x] = i;
		if(dis[to[i]]+1==dis[x]&&val[i]>0){
			ll temp = dfs(to[i],min(val[i],step-used));
			val[i] -= temp,val[i^1] += temp,used += temp;
			if(used==step||dis[s]>=inf) return used;
		}
	}
	if(--sum[dis[x]]==0) dis[s] = inf;
	sum[++dis[x]]++;
	return used;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	s=0,t=n+1; 
	for(i=1;i<=m;i++){
		cin>>x>>y>>l>>r;
		anss[i]=r,merge(x,y,r-l,i),merge(s,y,l,-1),merge(x,t,l,-1),ans+=l;
	}
	inf = t-s+1;
	sum[0] = inf;
	while(dis[s]<inf){
		for(i=0;i<inf;i++) cur[i]=la[i];
		ans-=dfs(s,1e18);
	}
	if(ans) cout<<"NO\n";
	else{
		cout<<"YES\n";
		for(i=1;i<=n;i++){
			for(j=la[i];j;j=ne[j]){
				if(id[j]!=-1) anss[id[j]]-=val[j];
			}
		}
		for(i=1;i<=m;i++) cout<<anss[i]<<endl;
	}
	return 0;
} 
/*
Input:
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

Output:
NO
*/

有源汇上下界网络可行流

定义

有一个 $n$ 个点 $m$ 条边的无向图，有源点和汇点。

对于每一条边都设置一个流量 $c$ 使得 $l \le c \le r$ 且对于每个点（除了源点和汇点）都要满足流量守恒。（$l$ 和 $r$ 是这条边的上下界）

这样的一组方案称为有源汇上下界网络可行流。

解决

考虑转化为无源汇上下界网络可行流，考虑连接 $t$ 到 $s$，边权无穷大，那么所有流量最后都会通过这条边回到 $s$ 点，那么对于 $s,t$ 两个点都满足了流量守恒性质。

然后按照无源汇上下界网络可行流计算方法计算即可，构造方案同理，但是此时可行流的大小是 $t$ 到 $s$ 那条边的流量。（不难想到）

代码就不放了，就是多了两个点和一条边。

有源汇上下界网络最大/小流

定义

有一个 $n$ 个点 $m$ 条边的无向图，有源点和汇点。

对于每一条边都设置一个流量 $c$ 使得 $l \le c \le r$ 且对于每个点（除了源点和汇点）都要满足流量守恒。（$l$ 和 $r$ 是这条边的上下界）

这样的一组使得流量最大/小的方案称为有源汇上下界网络最大/小流。

解决（最大流）

考虑先得到一组有源汇上下界网络可行流的答案。

那么有源汇上下界网络最大流就是在残量网络上继续跑最大流就可以了，证明不难。

跑最大流的时候一定要注意删去 $S$ 和 $T$ 的所有边并且删掉 $t$ 到 $s$ 的流量为无穷大的边，然后从原来的源点到汇点跑，并不是我们新建的源点和汇点。

代码中的 $S,T,s,t$ 变量稍有不同。

代码如下：

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

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll int
#define N 2000005
using namespace std;
ll n,m,s,t,inf,i,j,x[N],y[N],z[N],l[N],r[N],ans,temp,S,T,id[N],viss[N],summ;
ll la[N],ne[N],to[N],val[N],dis[N],cur[N],tot=1,sum[N],base;
inline void merge(ll x,ll y,ll z,ll idd){
	tot++,ne[tot] = la[x],la[x] = tot,to[tot] = y,val[tot] = z,id[tot] = idd;
	tot++,ne[tot] = la[y],la[y] = tot,to[tot] = x,val[tot] = 0,id[tot] = idd;
}
ll dfs(ll x,ll s,ll t,ll step){
	if(x==t) return step;
	ll used = 0;
	for(ll i=cur[x];i;i=ne[i]){
		cur[x] = i;
		if(viss[to[i]]||id[i]<base) continue;
		if(dis[to[i]]+1==dis[x]&&val[i]>0){
			ll temp = dfs(to[i],s,t,min(val[i],step-used));
			val[i] -= temp,val[i^1] += temp,used += temp;
			if(used==step||dis[s]>=inf) return used;
		}
	}
	if(--sum[dis[x]]==0) dis[s] = inf;
	sum[++dis[x]]++;
	return used;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m,S=1,T=n;
	s=0,t=n+1,merge(T,S,1e9,-2),base=-3;
	for(i=1;i<=m;i++){
		cin>>x[i]>>y[i]>>l[i]>>r[i];
		merge(x[i],y[i],r[i]-l[i],i),merge(s,y[i],l[i],-1),merge(x[i],t,l[i],-1),summ+=l[i];
	}
	inf = t-s+1;
	sum[0] = inf;
	while(dis[s]<inf){
		for(i=0;i<inf;i++) cur[i]=la[i];
		summ -= dfs(s,s,t,1e9);
	}
	if(summ!=0){
		cout<<"please go home to sleep\n";
		return 0;
	}
	for(i=la[T];i;i=ne[i]) if(to[i]==S&&id[i]==-2) ans+=(1000000000-val[i]);
	for(i=0;i<=n+2;i++) dis[i]=0,sum[i]=0;
	inf = n,sum[0] = inf,viss[s] = viss[t] = 1,base = 0;
	while(dis[S]<inf){
		for(i=1;i<=inf;i++) cur[i]=la[i];
		ans += dfs(S,S,T,1e9);
	}
	cout<<ans<<endl;
	return 0;
} 
/*
Input:
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

Output:
NO
*/

解决（最小流）

根据斜对称性，我们可以从 $t$ 跑到 $s$ 的最大流，用可行流的流量减去这个最大流的流量就是最小流的流量了。（可能为负）

代码就不放了，就改了几个变量。

上下界费用流

求满足上下界的网络流同时花费的费用最小/大。

很简单，不管是有源汇/无源汇建图都一样，但是要加上 $l \times cost$（底线要求）。

并且我们新连接的边边权都是 $0$，对应的跑最小/大费用最大流就可以了，并且因为没有流量的限制，甚至可以不用删边再跑一遍最大/小流。

代码以 4043 [AHOI2014/JSOI2014] 支线剧情 为例：

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

#include<bits/stdc++.h>
#define ll int
#define N 200005
using namespace std;
ll n,m,i,j,s,t,inf,x,y,z,ans,temp,deg[N],summ;
ll la[N],ne[N],to[N],val[N],dis[N],w[N],viss[N],vis[N],tot=1,q[N],he,ta;
inline void mergea(ll x,ll y,ll z,ll wal){
	tot++,ne[tot] = la[x],la[x] = tot,to[tot] = y,val[tot] = z,w[tot] = wal;
	tot++,ne[tot] = la[y],la[y] = tot,to[tot] = x,val[tot] = 0,w[tot] = -wal;
}
bool spfa(){
	for(ll i=0;i<=n+2;i++) dis[i]=2e9;
	q[he=ta=1]=s;
	dis[s]=0;
	while(he<=ta){
		ll tmp = q[he++];
		vis[tmp] = 0;
		for(ll i=la[tmp];i;i=ne[i]){
			if(val[i]>0&&dis[to[i]]>dis[tmp]+w[i]){
				dis[to[i]] = dis[tmp]+w[i];
				if(!vis[to[i]]) vis[to[i]]=1,q[++ta]=to[i];
			}
		}
	}
	return dis[t]<=1e9;
}
ll dfs(ll x,ll step){
	if(x==t) return step;
	viss[x] = 1;
	ll used = 0;
	for(ll i=la[x];i;i=ne[i]){
		if(viss[to[i]]) continue;
		if(dis[to[i]]==dis[x]+w[i]&&val[i]>0){
			ll temp = dfs(to[i],min(val[i],step-used));
			val[i] -= temp,val[i^1] += temp,used += temp;
			if(used==step) return used;
		}
	}
	return used;
}
ll solve(ll S,ll T,ll INF){
	s = S,t = T,inf = INF;
	ll ans = 0;
	while(spfa()){
		for(ll i=0;i<=n+2;i++) viss[i]=0;
		ans += dfs(s,1e9)*dis[t];
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>x;
		while(x--) cin>>y>>z,deg[i]--,deg[y]++,ans+=z,mergea(i,y,1e9,z);
	}
	for(i=2;i<=n;i++) mergea(i,n+1,1e9,0);
	for(i=1;i<=n;i++){
		if(deg[i]<0) mergea(i,n+2,-deg[i],0);
		if(deg[i]>0) mergea(0,i,deg[i],0);
	}
	mergea(n+1,1,1e9,0);
	ans += solve(0,n+2,n+3);
	cout<<ans<<endl;
	return 0;
} 
/*
Input:
6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0

Output:
24
*/

模拟网络流

模拟最大流

我们一般不直接模拟最大流（有的题目亦是如此），而是把它转化为最小割进行计算。

模拟最大流，就是利用各种手段（一般是 dp，或者其他的方式）来模拟网络流增加流的过程，但是如果是模拟最小割的话就是模拟割边的过程。

比如一道例题：

小明升任了 CF 国的大总管，他管辖的 $n$ 个城市，编号为 $1 \dots n$ 。每个城市生产了 $p_i$ 个货物，限制最多可以卖掉 $s_i$ 个货物。对于每两个城市 $i,j$，如果 $i<j$，则可以最多从 $i$ 运送 $c$ 个货物到 $j$ 。注意不能反向运送，却可以在多个城市之间送来送去。现在小明想知道，经过运输后，最多能卖掉多少个货物。

我们可以建出来图，图就是源点向所有点都连接了一条边权为 $p_i$ 的边，所有点都向汇点连接了一条边权为 $s_i$ 的边，然后每个 $i<j$ 都连接了 $c$ 的边。

图是十分规范的，我们可以用 dp 求解。

设 $dp_{i,j}$ 表示前 $i$ 个点，有 $j$ 个点到 $S$ 的边没有被割掉的最小花费，那么转移就是要么保留这个点到 $S$ 的边，要么保留这个点到 $T$ 的边就可以了，方程很好列出来：

$$
f_{i,j}=\min(f_{i-1,j}+p_i+c \times j,f_{i-1,j-1}+s_i)
$$

最后 $O(n^2)$ 就解决了，需要滚动数组优化，当然还有贪心的做法，此处就不强调了。

模拟费用流

这才是重点，模拟最大流的题很少，但是模拟费用流的题目却很多。

模拟费用流也是通过贪心等手段维护每次增广的流量以及反悔边的选择，一般需要用到优先队列，线段树等可删除结构，视具体的题目而定。

解决这种题可以从两个方面入手：

• 直接贪心。

• 建出来费用流的图，然后再根据反悔边判断，但是必须要保证增广次数乘上每次增广的代价可以忍受。

这种题需要多练习，可以参考一下 P5470 [NOI2019] 序列 题解 或者 P4217 [CTSC2010] 产品销售 题解，这两道题目一个是用了优先队列维护退流，一个是用了线段树维护流量，都是好的例子。

并且它们都是先建图，然后考虑各种反悔边，值得一提的是这些图一般都很有规律（忽略边权），便于维护。

还可以直接用贪心来做的题目，但是这个不是重点就跳过了。

那么，网络流就到此结束了。