zkw费用流学习笔记 - 洛谷保存站

### 参考博客：
[https://www.cnblogs.com/acha/p/6735037.html](https://www.cnblogs.com/acha/p/6735037.html)  
### 分析
&emsp;&emsp;普通的费用流每次都要做一遍spfa，最坏是$O(n*m)$,而zkw只需要$O(n+m)$即可完成一次标号，并且可以加上当前弧、多路增广、时间戳优化。  
### 做法
对于每次spfa结束，都有$D_i+w_{i,j}>=D_j(flow_{i,j}!=0)$。  
$D_i+w_{i,j}>=D_j \Leftrightarrow D_i-D_j+w_{i,j}>=0$  
又由于费用流是需要最短路的，因此每次dfs寻路时必须是$D_i-D_j+w_{i,j}=0$。  
设$V$是dfs后经过的点集，那么所有的边可以被分为四类：  
1. $i\in V , j\in V$
1. $i\in V , j\notin V$
1. $i\notin V,j\in V$
1. $i\notin V,j\notin V$

令$\Delta$为原图到新图$D$的变化量（只有$\in V$的会改变）。  
那么下面分别对这四种边进行分析。  
注：此处的该变量是负数,即$-\Delta$（当然也有改变量为正的写法）。
#### 第一种和第四种：
1：$D_i-D_j+w_{i,j}\ge0\Leftrightarrow D_i^\pi-D_j^\pi+w_{i,j}\ge0$  
4：同上  
$i\in V,j\in V$但是也有可能$j$不是由$i$增广到的，因此是$\ge$。
而$i\notin V,j\notin V$根据最短路定义可知也是$\ge$。  
因此这两种情况是对$\Delta$没有任何贡献的。  
#### 第二种：
$D_i-D_j+w_{i,j}\ge c\ >0\Leftrightarrow D_i^\pi-D_j+w_{i,j}>=c-\Delta>=0$  
那么可知$\Delta$是$\leq$满足所有第二种情况的$D_i-D_j+w_{i,j}$  
#### 第三种：
$D_i-D_j+w_{i,j}\ge0\Leftrightarrow D_i-D_j^\pi+w_{i,j}\ge\Delta$  
显然不和最短路定义矛盾。

---

综上我们可以发现$\Delta=min(D_i-D_j+w_{i,j})(\forall i\in V,\forall j\notin V,flow(i,j)>0)$

---

下面给出一道题目，普通费用流是过不了的啦。  
### LOJ P2979 「THUSCH 2017」换桌  
[题目传送门](https://loj.ac/problem/2979)  
&emsp;&emsp;由于本题建模与zkw费用流无关，在此稍稍带过。  
不难发现这种题都是套路。同一个桌子相邻座位连边，发现题目每个位置（不同桌子或相同桌子不同座位）能到达的桌子是一段区间，又是线段树优化建图的套路...  
&emsp;&emsp;不过此题需要两颗线段树一个表示到达左边，一个表示到达右边。因为是和距离差的绝对值成正比。  
&emsp;&emsp;之后套个zkw费用流即可AC此题，就当个zkw费用流板子题吧。  
#### 上代码：
```cpp
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=13000,M=130000,inf=1<<29;
int S,T,n,m,cnt;
namespace edge{
	int d[N],cur[N],nxt[M],to[M],cost[M],flow[M],tot;
	inline void add(int a,int b,int c,int e){to[++tot]=b,nxt[tot]=d[a],d[a]=tot,flow[tot]=c,cost[tot]=e;}
	inline void ins(int a,int b,int c,int e){add(a,b,c,e),add(b,a,0,-e);}
}using namespace edge;
namespace Dinic{
	int dis[N],Tim,maxflow,mincost;
	int vis[N];
	inline bool spfa(){
		memcpy(cur,d,sizeof(cur));
		static int x,i,mn;
		mn=inf;
		for(x=0;x<=cnt;++x)
			if(vis[x]==Tim)
			for(i=d[x];~i;i=nxt[i])
				if(flow[i]&&vis[to[i]]!=Tim)
					mn=min(mn,dis[x]-dis[to[i]]+cost[i]);
		if(mn>=inf)return 0;
		for(x=0;x<=cnt;++x)if(vis[x]==Tim)dis[x]-=mn;
		return 1;
	}inline int dfs(int now,int limit){
		if(!limit||now==T){mincost-=limit*dis[S],maxflow+=limit;return limit;}
		int fl=0,f,i,u;
		vis[now]=Tim;
		for(i=cur[now];~i;i=nxt[i]){
			u=to[i];
			cur[now]=i;
			if(dis[u]==dis[now]+cost[i]&&vis[u]!=Tim&&(f=dfs(u,min(limit,flow[i])))){
				fl+=f;
				limit-=f;
				flow[i]-=f;
				flow[i^1]+=f;
				if(!limit)break;
			}
		}return fl;
	}
	inline void work(){
		do{
			do{
				++Tim;
			}while(dfs(S,inf));
		}while(spfa());
	}
}using namespace Dinic;
int id[300][10];
namespace ST{
	const int C=1300;
	struct Segment_Tree{
		int p[C],q[C],pos;
		#define lc x<<1
		#define rc x<<1|1
		inline void build(int x,int L,int R){
			if(L==R){p[x]=q[x]=id[L][pos];return;}
			p[x]=++cnt,q[x]=++cnt;
			int mid=(L+R)>>1;
			build(lc,L,mid),build(rc,mid+1,R);
			ins(p[x],p[lc],inf,2*(R-mid));
			ins(p[x],p[rc],inf,0);
			ins(q[x],q[lc],inf,0);
			ins(q[x],q[rc],inf,2*(mid-L+1));
		}inline void Insert_0(int x,int L,int R,int ll,int rr,int from,int G){
			if(ll<=L&&R<=rr)return ins(from,p[x],inf,2*(G-R));
			int mid=(L+R)>>1;
			if(ll<=mid)Insert_0(lc,L,mid,ll,rr,from,G);
			if(rr>mid)Insert_0(rc,mid+1,R,ll,rr,from,G);
		}inline void Insert_1(int x,int L,int R,int ll,int rr,int from,int G){
			if(ll<=L&&R<=rr)return ins(from,q[x],inf,2*(L-G));
			int mid=(L+R)>>1;
			if(ll<=mid)Insert_1(lc,L,mid,ll,rr,from,G);
			if(rr>mid)Insert_1(rc,mid+1,R,ll,rr,from,G);
		}
	}a[10];
	inline void pre(){for(int i=0;i<10;++i)a[i].pos=i;}
}using namespace ST;
int L[300][10],R[300][10];
int main(){
	memset(d,-1,sizeof(d));
	tot=-1;
	S=0;T=++cnt;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			scanf("%d",&L[i][j]),id[i][j]=++cnt;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			scanf("%d",&R[i][j]);
	cnt+=n*m;
	pre();
	for(int i=0;i<m;++i)a[i].build(1,0,n-1);
	for(int i=0;i<n;++i){
		for(int j=0;j<m-1;++j)
			ins(id[i][j],id[i][j+1],inf,1),ins(id[i][j+1],id[i][j],inf,1);
		ins(id[i][0],id[i][m-1],inf,1),ins(id[i][m-1],id[i][0],inf,1);
	}for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			ins(S,id[i][j]+n*m,1,0),ins(id[i][j],T,1,0);
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j){
			if(L[i][j]<=i)a[j].Insert_0(1,0,n-1,L[i][j],min(i,R[i][j]),id[i][j]+n*m,i);
			if(R[i][j]>i)a[j].Insert_1(1,0,n-1,max(L[i][j],i+1),R[i][j],id[i][j]+n*m,i);
		}
	work();
	if(maxflow<n*m)printf("no solution\n");
	else printf("%d\n",mincost);
	return 0;
}

```

正在渲染内容...