像这种“传纸条”类的经典题目，基本上已经有成熟的算法了：
1.DP
2.费用流

DP解法主要是对付K<=2的（我目前只知道一个复杂度为O(N^(K+1))的DP，若有大牛
有好解法，欢迎讨论）
于是，召唤出费用流。
建图：为方便，每个格子掰成两个点，分别叫“出点”，“入点”，
入点到出点间连一个容量1，费用为格子中数的边，以及一个容量∞，费用0的边。
同时，一个格子的“出点”向它右、下的格子的“入点”连边，容量∞，费用0。

源点向（0，0）的入点连一个容量K的边，(N-1,N-1)的出点向汇点连一个边。
当然，也可以用替代做法：限定只增广K次。

费用流的代码：

struct edge{
	int e,c,f;
	edge *next,*opt;
};
int BellmanFord(int S,int T){
	int top,bot,x,ret;
	for (int i=0;i<NN;i++)dis[i]=-1,inQ[i]=0;
	inQ[queue[top=0]=S]=1;bot=1;
	dis[S]=0;pre[S]=-1;prep[S]=NULL;
	while (top!=bot){x=queue[top++];if (top>=((NMax*NMax)<<1)+1)top=0;
		inQ[x]=0;
		for (edge *p=E[x];p;p=p->next)
			if (p->f && dis[p->e]<dis[x]+p->c){
				dis[p->e]=dis[x]+p->c;
				pre[p->e]=x;prep[p->e]=p;
				if (!inQ[p->e]){
					inQ[queue[bot++]=p->e]=1;
					if (bot>=((NMax*NMax)<<1)+1)bot=0;
				}
			}
	}
	if (dis[T]==-1)return 0;
	x=T;ret=0;
	while (x!=S){
		ret+=prep[x]->c;prep[x]->f--;prep[x]->opt->f++;
		x=pre[x];
	}
	return ret;
}
int MaxKFlow(int S,int T,int k){
	int ret;
	ret=0;
	while (k--)ret+=BellmanFord(S,T);
	return ret;
}

• Re:雁过留声——最大费用流 (1238) wx5391805 2011-07-01 00:53:31
• Re:雁过留声——最大费用流 (10) weihaohaoren 2012-01-26 18:36:04
• Re:雁过留声——最大费用流 (70) weihaohaoren 2012-01-26 19:50:28