标签：增广 ll 源点网络流量汇点 dis

当学习笔记用，持续更新。

写给自己看的，图有点少。如果有人真想通过这篇博客学网络流的话也不是不行……

~~因为更新极慢无比，所以这篇博客里的各份代码码风可能会出现巨大的差别。~~

关于学习途径

显然有无数人在自学网络流的时候因为网上大部分题解的姿势都过于抽象而被劝退，所以提一下。可作参考。

入门网络流的话建议看某 18 年日报，虽然没有具体的复杂度之类的证明，但是确实可以包你看懂，至少理解最大流算法什么的基本思想是够了。

然后讲解最严谨知识点最全面例题最多的一篇应该是 Alex_Wei 神仙的，但是阅读起来不太友好。

本篇博客尽量取个平均值。（？）

定义

大概包含我在内的不少人最开始就是被网络流的巨大丑定义劝退的。

比较优雅地说就是：

我们把城市抽象成一张有向图。
图上有很多很多的节点，其中有一个源点 \(s\) 和一个汇点 \(t\)。（后面会出现无源汇）
把连接每个点的水管抽象为有向边，它们都有一个容量 \(c(i,j)\)。
假设整座城市只有你一个无业游民，你在汇点等着喝水。
现在水厂在源点放水，水会顺着边的方向不停的流，一路流向你所在的汇点。
一条边的流量 \(f(i,j)\) 就是这条边里流了多少水，而且这条边的流量不能超过容量，不然它就爆了。
因为每个点都不会漏水，所以流进一个点的流量和流出这个点的流量是相等的。
水厂不想浪费水，需要让流出来的所有水都进你嘴里，于是规定流出源点和流进汇点的流量相等，那么这个流进汇点的流量就叫整张网络的流量。

其它的一些定义和性质要用再提。

网络最大流

你想在汇点喝到尽量多的水，那你就需要通过规划每条边里流多少水来使这个网络的流量最大。现在我们需要一些算法来求出这个最大流量。

因为有着容量限制，这个问题并没有那么简单。

EK

增广路：从源点到汇点的一条使得当前流量可以增加的路径。
剩余流量：一条边的容量减去流量，即还能流多少水。
残量网络：剩余流量不为 \(0\) 的边组成的网络。

EK 就是直接通过 bfs 不停地找增广路，直到实在找不到了（即源汇点在残量网络上不连通）为止。bfs 时需要跳过那些已经被流满的边。

先不管它看上去对不对哈，考虑一下这玩意怎么实现。

显然每次找到的增广路的流量就是这条路径上的边的剩余流量的最小值，那么我们每次就把增广路上的边的剩余流量减去整条增广路的流量，不断重复这个过程，直至没有任何不经过剩余流量为 \(0\) 的边到达汇点的路径，即没有增广路了，那么求出来的增广路流量之和就是答案。

然而用脖子都能想到这么直接做有很大概率出来的不是最大流，所以我们要做一点处理，使得 EK 在跑的过程中可以不断修正流方案。

也就是建反边。我们每次确定一条增广路，就使路径上的所有边的反边容量加上目前这条增广路的流量，表示这条边上的流量有多少是可以被撤销的，显然初值是 \(0\)。

这样当我们以后再走到这里时，从反边走过来，就可以看作是把之前从正边流过去的流量匀回来，就当作没流过这条边（或者是没流过那么多），同样进行容量加减处理。这样就达到了撤销效果。

然后关于怎么建反边：设正边编号为 \(2i\)，反边编号为 \(2i+1\)，那么正边编号异或一下 \(1\) 就是反边了，在建图的时候把编号带进边里，其它信息放在外面即可。

于是跑就完啦。

这个撤销机制相当有用，后面会不停地用到。

然后因为使用了 bfs，这样保证了每次找到的增广路经过的边都是最少的，于是时间复杂度理论上是 \(O(nm^2)\)（也就是说如果你随便乱找增广路的话复杂度是假的……）。我不会证，可以看上面 Alex_Wei 博客的证明。不过很明显这玩意很难跑满，如果不是出题人故意卡你的话理论上点数在 \(10^3\sim 10^4\) 规模的网络它都能跑。

然后你就可以愉快地 AC 掉 P3376 和 P2740 了。

const ll I=1e18,N=207,W=1e4+7;
ll n,m,s,t,ans;
ll u[W],v[W],w[W],val[W];
ll vis[N],pth[N],lst[N];
vector<pll > e[N];
bool bfs() {
	memset(vis,0,sizeof(vis));
	queue<ll> q;
	q.push(s),vis[s]=1;
	while (!q.empty()) {
		ll p=q.front();
		q.pop();
		if (p==t) return 1;
		for (pll i:e[p]) if (!vis[i.first]&&val[i.second])
			vis[i.first]=1,pth[i.first]=i.second,lst[i.first]=p,q.push(i.first);
	}
	return 0;
}
void EK() {
	while (bfs()) {
		ll res=I;
		for (ll i=t;i!=s;i=lst[i]) res=min(res,val[pth[i]]);
		for (ll i=t;i!=s;i=lst[i]) val[pth[i]]-=res,val[pth[i]^1]+=res;
		ans+=res;
	}
}
int main() {
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for (ll i=1;i<=m;i++)
		scanf("%lld%lld%lld",&u[i],&v[i],&w[i]),val[i*2]=w[i],
		e[u[i]].pb({v[i],i*2}),e[v[i]].pb({u[i],i*2+1});
	EK();
	cout<<ans;
	return 0;
}

Dinic

但是感觉 EK 不够快啊，看看有没有可以优化的地方。

回顾 EK 的过程，发现它每次 bfs 居然只能找出一条增广路，那不在增广路上的信息是不是白白浪费了啊，有点可惜，考虑把它们利用起来，一次多求几条增广路。

首先我们跑一遍 bfs。

EK 里决定当前状态一个点是否可能流向另一个点的条件是在去掉已经流满的边的情况下，另一个点与源点的距离是否等于这个点的距离加一，即是否可能在一条 bfs 路径上。而这些距离信息是一次 bfs 就可以知道的。

那我们是不是可以直接知道在当前的 bfs 条件下，有哪些点之间是可能有流量的，然后一次性榨干目前状态下的所有增广路呢？

所以知道了每个点与源点的距离（深度）之后，我们可以再用几次从源点开始的 dfs，同样用 EK 的建反边处理，找出目前能走的所有的增广路。这样一次 bfs 就能找出巨大多的增广路，实在是美哉！

这时还能流水的边可能会减少，于是再跑一遍 bfs 求出找完增广路的网络的深度信息，再 dfs……不断重复以上过程直到 dfs 找不出增广路为止。

于是我们学会了 Dinic。

但它比 EK 难写诶，而且这又 bfs 又 dfs 的，真的能比 EK 快吗？

还真不一定。

那它有啥用啊。

但是它能优化啊。

多路增广

发现一次 dfs 只能找出一条增广路好像跟 EK 没有什么差别，不如用一次 dfs 全部找出来，因为 Dinic 使你可以确定当前所有可以流的边。

也就是在 dfs 的过程中记目前这个点还有多少流量能用，回来的时候不用从头再找，继续用剩下的流量从这个点开始走去找即可。

当前弧优化

发现我们很可能大量地重复遍历了已经流满的路径。这个流满指的并不是一个点的出边被流满，而是从这个出边流出去会在后面被阻断，没法再流到汇点了。这个你无法快速判断，很不好。

发现由于 dfs 找增广路的特性，如果走完了一条边然后出来，之后如果再从这条边过去（注意正向反向边这里不看成同一条），是不会对流量产生任何贡献的。所以可以对每个点记录一下上次走了哪条边，下一次 dfs 到这直接接着记录的边再搜。

用链式前向星就记上次的边的编号，每次重新开始就把它当做 head 搞。

用 vector 就记上次的边的下标，下次从它开始。

注意这里不是跳过当前弧，因为当前弧上的边有可能还没流满，还能再流，是从当前弧开始继续搜。

（所以当前弧这个名字应该指的就是目前搜到的从源点开始的路径吧？）

在上面两个优化的加持下，Dinic 的效率直接起飞。理论大概是 \(O(n^2m)\)，在稠密图上可以吊打 EK。而且似乎各位出题人都默认不卡这个，能跑 \(10^4\sim 10^5\) 规模的网络。

然而不加这俩优化或者优化写错就可能跑得还没 EK 快，需要注意。

有些东西就不需要在 bfs 的时候记了，没难写多少。

ll n,m,s,t;
ll u[W],v[W],w[W],val[W];
ll dis[N],cur[N];
vector<pll > e[N];
bool bfs() {
	memset(dis,-1,sizeof(dis)),memset(cur,0,sizeof(cur));
	queue<ll> q;
	q.push(s),dis[s]=0;
	while (!q.empty()) {
		ll p=q.front();
		q.pop();
		if (p==t) return 1;
		for (pll i:e[p]) if (dis[i.first]==-1&&val[i.second])
			dis[i.first]=dis[p]+1,q.push(i.first);
	}
	return 0;
}
ll dfs(ll p,ll fl) {
	if (p==t) return fl;
	ll pf=0;
	for (ll ii=cur[p];ii<e[p].size();ii++) { pll i=e[p][ii];
		cur[p]=ii;
		if (val[i.second]&&dis[i.first]==dis[p]+1) {
			ll nf=dfs(i.first,min(fl-pf,val[i.second]));
			if (nf) {
				pf+=nf,val[i.second]-=nf,val[i.second^1]+=nf;
				if (pf==fl) break;
			}
		}
	}
	return pf;
}
ll din() {
	ll res=0;
	while (bfs()) res+=dfs(s,J);
	return res;
}
void mian() {
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for (ll i=1;i<=m;i++)
		scanf("%lld%lld%lld",&u[i],&v[i],&w[i]),val[i*2]=w[i],
		e[u[i]].pb({v[i],i*2}),e[v[i]].pb({u[i],i*2+1});
	cout<<din();
}

其它的玩意

好像还有更快的 ISAP 什么的东西，有机会再写。

封装

考虑到网络流这玩意一般就单纯用来建个模跑个最大流费用流啥的然后就扔了，单独弄一堆数组什么的去开一遍似乎不太优雅，所以个人认为封装一下用起来会舒服很多。

namespace din {
	const int N=207,W=1e4+7;
	int n,m,s,t,cur[N];
	ll dis[N],val[W],ans;
	vector<pii > e[N];
	bool bfs() {
		memset(dis,-1,sizeof(dis)),memset(cur,0,sizeof(cur));
		queue<int> q;
		q.push(s),dis[s]=0;
		while (!q.empty()) {
			int p=q.front();
			q.pop();
			if (p==t) return 1;
			for (pii i:e[p]) if (dis[i.fi]==-1&&val[i.se])
				dis[i.fi]=dis[p]+1,q.push(i.fi);
		}
		return 0;
	}
	ll dfs(int p,ll fl) {
		if (p==t) return fl;
		ll pf=0;
		for (int ii=cur[p];ii<e[p].size();ii++) { pii i=e[p][ii];
			cur[p]=ii;
			if (val[i.se]&&dis[i.fi]==dis[p]+1) {
				ll nf=dfs(i.fi,min(fl-pf,val[i.se]));
				if (nf) {
					pf+=nf,val[i.se]-=nf,val[i.se^1]+=nf;
					if (pf==fl) break;
				}
			}
		}
		return pf;
	}
	void main() { while (bfs()) ans+=dfs(s,J); }
	void ini(int _n,int _s,int _t) { n=_n,s=_s,t=_t,m=1,ans=0; }
	void add(int x,int y,ll z,bool typ) { val[++m]=z,e[x].pb({y,m}),val[++m]=0,e[y].pb({x,m}); }
}
ll n,m,s,t;
void mian() {
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	din::ini(n,s,t);
	for (ll i=1,x,y,z;i<=m;i++) scanf("%lld%lld%lld",&x,&y,&z),din::add(x,y,z,1);
	din::main();
	cout<<din::ans;
}

应用

有个叫网络流 24 题的东西。应该包含了网络流的一些基础题目。

里面的题要用再讲。

P2756 飞行员配对方案问题

这玩意一眼二分图最大匹配，实际上也是可以用网络流做的。

如果源点向每个左部点，每个点向汇点连一条容量为 \(1\) 的边，然后每条原图中的边容量也设为 \(1\)，那么跑一遍最大流就是答案了。

至于这种神秘的建图方法都是怎么想到的：或许是这种“每个人只能选一种配对方案”的限制让发明者联想到了网络流的容量限制吧……

用 Dinic 跑二分图匹配会比匈牙利快得多，是 \(O(n\sqrt{m})\) 的，实际还是跑不满。

ABC320G Slot Strategy 2 (Hard)

具体细节先不管，反正可以转化成一个二分图多重匹配问题，即每个点最多可以连 \(c_i\) 条边。

可以魔改匈牙利（即一个右部点被占用仅当连接边数达到 \(c_i\)，否则枚举它连的所有边尝试匹配），不过也可以把上面每个点与源点或汇点连之间的边改为对应的 \(c_i\) 再跑最大流。

……

最小费用最大流

EK & Dinic

看我们用这么一堆管子居然获得了如此之大的流量，黑心水厂不开心了，于是规定：第 \(i\) 条管子里每流一单位水就要向他们支付 \(c_i\) 的费用。

作为一位心系人民的 OIer，你肯定要坚持底线，不让流量变动丝毫。但是为了节省经费，你需要在流量不变的前提下找到最小费用。这就是最小费用最大流问题。

其实相当简单啊。我们只要保证在目前的状态下，所有水都流在从源点出发的关于单位水的费用的最短路上，等到有管道的容量被榨干再重新求一遍最短路，反复执行下去直到找不到增广路为止。这样就能保证费用最小。

所以只要把 bfs 换成 spfa 即可。

Dijkstra 不行吗？

注意这里反向边的花费是正向边的相反数，相当于走回去就督促甲方退钱，所以 Dijkstra 跑不了。不过好像确实有一个叫 Primal-Dual 的东西可以做到 Dijkstra 求解最小费用最大流，但是一般也没哪个缺德的出题人会在网络流里卡 SPFA……

但也只是一般而已，还真有人卡过。晚点会写。

对于 EK，增广路就是每次 spfa 搜到的源点到汇点的路径。

对于 Dinic，一条增广路合法仅当路径上所有相邻的点 \(u,v\) 均满足 \(dis_u+d_{u,v}=dis_v\)，其中 \(dis_i\) 表示源点到 \(i\) 的最短路，\(d_{i,j}\) 表示两点间边的长度。就是最大流改一下。但是 Dinic 有个坑啊，这么写的话遇到费用为 \(0\) 的边时，它会去死，所以要再开个标记记一下这个点是否被 dfs 过，回溯时记得撤销，否则会导致时间复杂度不太对。

于是你就可以愉快地过掉 P3381 了。

EK：

ll n,m,s,t,ans1,ans2;
ll u[W],v[W],w[W],c[W],val[W],cs[W];
ll vis[N],pth[N],lst[N],dis[N];
vector<pll > e[N];
bool spfa() {
	memset(vis,0,sizeof(vis)),memset(dis,45,sizeof(dis));
	queue<ll> q;
	q.push(s),vis[s]=1,dis[s]=0; 
	while (!q.empty()) {
		ll p=q.front();
		q.pop();
		vis[p]=0;
		for (pll i:e[p]) if (dis[i.first]>dis[p]+cs[i.second]&&val[i.second]) {
			dis[i.first]=dis[p]+cs[i.second];
			pth[i.first]=i.second,lst[i.first]=p;
			if (!vis[i.first]) vis[i.first]=1,q.push(i.first);
		}
	}
	return dis[t]<I;
}
void EK() {
	while (spfa()) {
		ll res=I;
		for (ll i=t;i!=s;i=lst[i]) res=min(res,val[pth[i]]);
		for (ll i=t;i!=s;i=lst[i]) val[pth[i]]-=res,val[pth[i]^1]+=res;
		ans1+=res,ans2+=res*dis[t];
	}
}
int main() {
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for (ll i=1;i<=m;i++)
		scanf("%lld%lld%lld%lld",&u[i],&v[i],&w[i],&c[i]),
		val[i*2]=w[i],cs[i*2]=c[i],cs[i*2+1]=-c[i],
		e[u[i]].pb({v[i],i*2}),e[v[i]].pb({u[i],i*2+1});
	EK();
	cout<<ans1<<" "<<ans2;
	return 0;
}

Dinic：

ll n,m,s,t;
ll u[W],v[W],w[W],c[W],val[W],cs[W];
ll dis[N],vis[N],cur[N],ans1,ans2;
vector<pll > e[N];
bool spf() {
    memset(vis,0,sizeof(vis)),memset(dis,20,sizeof(dis)),memset(cur,0,sizeof(cur));
    queue<ll> q;
    q.push(s),vis[s]=1,dis[s]=0;
    while (!q.empty()) {
        ll p=q.front();
        q.pop();
        vis[p]=0;
        for (pll i:e[p]) if (dis[i.first]>dis[p]+cs[i.second]&&val[i.second]) {
            dis[i.first]=dis[p]+cs[i.second];
            if (!vis[i.first]) vis[i.first]=1,q.push(i.first);
        }
    }
    return dis[t]<J;
}
ll dfs(ll p,ll fl) {
	if (p==t) return fl;
	vis[p]=1;
	ll pf=0;
	for (ll ii=cur[p];ii<e[p].size();ii++) { pll i=e[p][ii];
		cur[p]=ii;
		if (!vis[i.first]&&val[i.second]&&dis[i.first]==dis[p]+cs[i.second]) {
			ll nf=dfs(i.first,min(fl-pf,val[i.second]));
			if (nf) {
				pf+=nf,val[i.second]-=nf,val[i.second^1]+=nf;
				if (pf==fl) break;
			}
		}
	}
	vis[p]=0;
	return pf;
}
void din() {
	ll res;
	while (spf()) res=dfs(s,J),ans1+=res,ans2+=res*dis[t];
}
void mian() {
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
	for (ll i=1;i<=m;i++)
		scanf("%lld%lld%lld%lld",&u[i],&v[i],&w[i],&c[i]),
		val[i*2]=w[i],cs[i*2]=c[i],cs[i*2+1]=-c[i],
		e[u[i]].pb({v[i],i*2}),e[v[i]].pb({u[i],i*2+1});
	din();
	cout<<ans1<<" "<<ans2;
}

Dijkstra 费用流

就是上面提到的 Primal-Dual。

需要用到一些 Johnson 的思想，晚点更新。

最大费用最大流

反过来变成最小费用。注意这时这个图很可能有负环。

有负环费用流

在后面上下界网络流那一块。

应用

P1251 餐巾计划问题

离谱的建模方法：

流即为毛巾。
源点提供各种毛巾，汇点收集干净毛巾然后变成脏毛巾丢给源点，由于流量守恒，这样不会有毛巾被弄丢，可以理解成是毛巾通过汇点流回了源点。
每天拆成早上和晚上两个点，以区分干净和脏毛巾。
规定每条毛巾在洗好之后立刻开始用，如果要晚点用就等完再洗。
提供所需干净毛巾：每天早上向汇点连边，容量为当天 \(r_i\)，费用为 \(0\)。
生产脏毛巾：源点向每天晚上连边，容量为当天 \(r_i\)，费用为 \(0\)。
留着脏毛巾之后再处理：每天晚上向下一个晚上连边，容量为 \(\inf\)，费用为 \(0\)。
买毛巾：源点向每一天早上连边，容量为 \(\inf\)，费用为 \(p\)。
慢洗部：每天晚上向 \(m\) 天后的早上连边，容量为 \(\inf\)，费用为 \(f\)。
快洗部：每天晚上向 \(n\) 天后的早上连边，容量为 \(\inf\)，费用为 \(s\)。
由于只有前两类边有容量限制，所以跑最大流肯定能把这两类边全部流满，也就是保证每天的毛巾都够用。在此基础上再去保证费用最小。
也就是在这个网络上跑费用流。

通常费用流的用法是，用最大流满足题目限制，用最小费用满足答案最优。

比如这里，最小费用满足费用最小，那最大流就应该用来满足每天毛巾够用了。

利用流量守恒表示物品个数不变应该算个套路罢。

……

最小割

水厂的黑心甲方们不高兴了，于是要阻止我们喝水。他们需要通过割断一些水管来使水无法从源点流到汇点。但是水厂的经费也有限，所以他们要使割掉的水管容量和最小。这个容量和叫最小割。

最大流最小割定理：最大流等于最小割。

口胡一下。

所有割都不小于最大流：

给一种感性理解。

每割掉一条边最多只会使整张网路的流量减少这条边的容量，即极限情况是这条边被流满了，而且没有其它的边还可流。显然你割这里不可能会使其它地方的流量变少。

那割到最后，割掉的边容量之和肯定不会还没最大流大。

存在一组割等于最大流：

反证，假设达到最大流的时候残量网络还连通，那么还可以继续增广，所以这时求出的不是最大流，矛盾。

所以回想一下，之前 EK 和 Dinic 判断是否达到最大流的条件就是源汇点是否在残量网络上连通，即还有没有增广路。

应用

……

上下界网络流

见黑心水厂这么黑心，我们果断放弃，换了一个良心水厂。现在我们可以喝水了。

然而良心水厂也有一个要求：如果一条水管里几乎不流水，那么这会使得建筑方觉得它们辛辛苦苦打下的管子白费了，良心水厂觉得这不好，于是要求第 \(i\) 条水管至少要流 \(b_i\) 的水。

然后就可以引出一大堆问题。

无源汇上下界可行流

？我是谁？我在哪？水厂又在哪？

也就是说水厂在水管里放了一点违反了能量守恒定律的水就跑了，这些水在管子里不停的流，也就是说每个点都需要满足流进的水量等于流出的水量，即流守恒。我们需要规划一种流的方案使得它符合水厂的要求，咋办？

首先我们钦定每条边的下限都被流满了，然后将新的流量设为上限减去下限，再去考虑咋流。主要问题在于流满下限之后，每个点的流守恒很可能当场就没了，所以我们要做一些处理。

考虑把流不守恒的情况转化掉。虚空建一个超级源点和一个超级汇点，然后对每个点连边。如果一个点漏水就把漏的水量连到汇点上，多了水就让源点连过来负责加对应的水量，正好守恒就不管它。

这个时候再对这张每条边容量已经更换为上界减去下界，而且加上了超源超汇的图跑最大流。如果从源点出发的边存在没流满的，那说明不守恒的问题无法解决（即还没流满就增广不了了），不存在可行流；否则目前原图中的边流的方案即是一组可行流。

有源汇上下界可行流

水厂突然回来放水了。

相比无源汇的变化在于源点和汇点可以不满足流守恒，那就从原图中的汇点到源点连一条容量为 \(inf\) 的边（不是源点到汇点），把多出的流量匀回来，强制让它变成变成一个无源汇，再按上面的方法跑即可。

流量不是跑出来的最大流，应该是汇点到源点的无限边里的流量（或者反边的容量）。

有源汇上下界最大流

先跑一遍可行流，然后在跑完可行流后，撤掉超级源汇点和无限容量边，从源点到汇点再跑出一个最大流即可。答案是可行流量加上从源点到汇点的新最大流。

换句话说，加上超级源汇和无限边后用超源超汇跑一遍最大流，检查一下有没有流满然后把它们撤掉用原源原汇再跑一次最大流，两次加起来。

这时因为容量已经更换为上界减去下界，我们又用可行流提前规划好了一种可行的流法，那么最大流在上面怎么反悔都不会打破限制，还可以帮你完成一切的撤销工作，确保是最大流。

有源汇上下界最小流

最小流不是 \(0\) 吗？……哦。

最大流的从源点到汇点再跑一次最大流是看还有什么流量还可以加。

那我们是不是从汇点到源点跑一次看还有什么流量可以减就行了？

所以就是可行流量减去从汇点到源点的新最大流。

有源汇上下界费用流

一样地换成 spfa 啦。注意一开始找可行流要的费用也得加上。

应用

P7173 【模板】有负圈的费用流

你会发现你的 SPFA 或者 Dijkstra 跑着跑着就死了，所以我们要开点外挂。

利用网络流的反悔性质，在跑费用流之前先把每条负费用边流满是没有关系的。这时把它们的反边容量一样进行增加，费用是原边的相反数。然后图上就没有负边了，要改就等着后面流过来的时候反悔掉。

但是你要是搁这满流的时候把网络的流量守恒干没了也没法反悔啊，所以用回有源汇上下界网络流的思路，建超源超汇和无限边，少流量了用超源补，多流量了补给超汇，确保没有负权边后先跑一遍费用流。让网络暂时变得流量守恒，接下来把超源超汇撤掉，一切交给第二次费用流。

注意一开始处理满流的时候依然要计算费用。

P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

建模是好想的。

照片是流。
源点向每个少女连容量为 \([G_x,\inf]\) 的边。
每天可以拍的少女向这一天连容量为 \([L_{k_i},R_{k_i}]\) 的边。
每天向汇点连容量为 \([0,D_i]\) 的边。

跑一遍上下界。

namespace din {
	const int N=2007,W=2e5+7;
	int n,m,s,t,cur[N];
	ll flw[N],val[W],dis[N],ans;
	vector<pii > e[N];
	bool bfs() {
		memset(dis,-1,sizeof(dis)),memset(cur,0,sizeof(cur));
		queue<int> q;
		q.push(s),dis[s]=0;
		while (!q.empty()) {
			int p=q.front();
			q.pop();
			if (p==t) return 1;
			for (pii i:e[p]) if (dis[i.fi]==-1&&val[i.se])
				dis[i.fi]=dis[p]+1,q.push(i.fi);
		}
		return 0;
	}
	ll dfs(int p,ll fl) {
		if (p==t) return fl;
		ll pf=0;
		for (int ii=cur[p];ii<e[p].size();ii++) { pii i=e[p][ii];
			cur[p]=ii;
			if (val[i.se]&&dis[i.fi]==dis[p]+1) {
				ll nf=dfs(i.fi,min(fl-pf,val[i.se]));
				if (nf) {
					pf+=nf,val[i.se]-=nf,val[i.se^1]+=nf;
					if (pf==fl) break;
				}
			}
		}
		return pf;
	}
	void main() { while (bfs()) ans+=dfs(s,J); }
	void ini(int _n,int _s,int _t) {
		n=_n,s=_s,t=_t,m=1,ans=0,memset(flw,0,sizeof(flw));
		for (ll i=0;i<=_n;i++) e[i].clear();
	}
	void add(int x,int y,ll z) { val[++m]=z,e[x].pb({y,m}),val[++m]=0,e[y].pb({x,m}); }
	void add(int x,int y,ll a,ll b) { add(x,y,b-a),flw[x]-=a,flw[y]+=a; }
	void solve(int _n,int _m) {
		for (int i=0;i<=_n+_m+1;i++) {
			if (flw[i]>0) add(s,i,flw[i]);
			else if (flw[i]<0) add(i,t,-flw[i]);
		}
		add(_n+_m+1,0,I);
		main();
		ans=val[m];
		for (pii i:e[s]) if (val[i.se]) return ans=-1,void();
		val[m-1]=val[m]=0,s=0,t=_n+_m+1;
		main();
	}
}
ll n,m,g[W];
vector<pii > e[N];
void mian() {
	din::ini(n+m+3,n+m+2,n+m+3);
	for (ll i=1;i<=m;i++) scanf("%lld",&g[i]),din::add(0,i,g[i],I);
	for (ll i=1,c,d;i<=n;i++) {
		scanf("%lld%lld",&c,&d);
		din::add(m+i,n+m+1,0,d);
		for (ll t,l,r;c--;) scanf("%lld%lld%lld",&t,&l,&r),t++,din::add(t,m+i,l,r);
	}
	din::solve(n,m);
	cout<<din::ans<<"\n\n";
}

……

练习题

（to be continued）

标签：增广,ll,源点,网络,流量,汇点,dis
From： https://www.cnblogs.com/CarroT1212/p/18011131/Flows

网络流