费用流

POJ 3422

---

• K格取数问题
• 算是费用流的一个模板题，同时也巩固了上节学习的拆点套路。
• 为了保证每个数的权值只被计算一次，并且可以走K条路，我们需要用到拆点。每一个点拆成一个出点和入点，出点到入点建一条容量为1，权值为a（i，j）的边，再建一条容量为k-1，权值为0的边，这样就保证了一个点的权值最多被计算一次。
• 对于每个出点，只需要向它右边和下放的两个点分别连一条容量为k权值为0的边即可。
• s为（1,1）的入点，t为（n，n）的出点，跑最大费用流即可。
• 什么？你不会费用流？

费用流

---

• 我们在求最大流的时候方案并不是唯一的。在费用流问题中，边不仅有容量，还有单位权值。比如边i的单位权值为cost（x，y），这条边你通了流量为d的流，那么费用就是d*cost（x，y）。
• 费用流问题我们是在保证方案是最大流的情况下求最小费用或者最大费用。
• 可以回想我们之前的Krap算法，每次只找到一条s~t的增广路，而这条路径上所有边流量相同，所以产生的费用应该是sigma（cost（x，y））*flow。所以我们可以修改Krap算法，让原本简单的跑bfs变成跑最长路即可。

Coding

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+10;
int n,k,ans,tot,s,t,ver[N],Next[N],lin[N],edge[N],e[N],v[N],incf[N],pre[N],d[N];
void add(int x,int y,int c,int cost){
	ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=c;e[tot]=cost;
	ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0;e[tot]=-cost;
}
bool spfa(){
	queue<int>q;
	memset(d,0xcf,sizeof(d));
	memset(v,0,sizeof(v));
	q.push(s),v[s]=1,d[s]=0;
	incf[s]=1<<29;
	while(q.size()){
		int x=q.front();q.pop();v[x]=0;
		for(int i=lin[x];i;i=Next[i]){
			if(edge[i]){
				int y=ver[i];
				if(d[y]<d[x]+e[i]){
					d[y]=d[x]+e[i];
					incf[y]=min(incf[x],edge[i]);
					pre[y]=i;
					if(!v[y]) v[y]=1,q.push(y);
				}
			}
		}
	}
	if(d[t]==0xcfcfcfcf)
	return 0;
	return 1;
}
void update(){
	int x=t;
	while(x!=s){
		int i=pre[x];
		edge[i]-=incf[t];
		edge[i^1]+=incf[t];
		x=ver[i^1];
	}
	ans+=incf[t]*d[t];
}
int main(){
	tot=1;
	scanf("%d%d",&n,&k);
	s=1,t=n*n*2;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j){
		int x;scanf("%d",&x);
		int now=(i-1)*n+j;
		add(now,now+n*n,1,x);add(now,now+n*n,k-1,0);
		if(j<n)
		add(now+n*n,now+1,k,0);
		if(i<n)
		add(now+n*n,now+n,k,0);
	}
	while(spfa()) update();
	printf("%d\n",ans);
	return 0;
}