题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3376

http://acm.hdu.edu.cn/showproblem.php?pid=2686

http://poj.org/problem?id=3422

POJ 3422为从矩阵左上角走到右下角，最多走k次，每个格子里的数字只能算一次，后面可以重复经过，求经过的各个数字的和的最大值。

拆点，入点向出点连流量为1，费用为当前格子负值的边，向下方，右方连边，流量为k，费用为0，起点连流量为1，源点向1连边，m*m向汇点连边，流量为k，费用为0.

跑费用流。

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/17 9:42:51
File Name :6.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 100000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=10000;
const int maxm=500100;
struct Edge{
	int next,to,cap,cost;
	Edge(int _next=0,int _to=0,int _cap=0,int _cost=0){
		next=_next;to=_to;cap=_cap;cost=_cost;
	}
}edge[maxm];
int head[maxn],vis[maxn],pre[maxn],dis[maxn],n,tol;
void addedge(int u,int v,int cap,int cost){
	edge[tol]=Edge(head[u],v,cap,cost);head[u]=tol++;
	edge[tol]=Edge(head[v],u,0,-cost);head[v]=tol++;
}
bool spfa(int s,int t){
	queue<int> q;
	for(int i=0;i<=n;i++)
		dis[i]=INF,vis[i]=0,pre[i]=-1;
	dis[s]=0;vis[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			if(edge[i].cap&&dis[v]>dis[u]+edge[i].cost){
				dis[v]=dis[u]+edge[i].cost;
				pre[v]=i;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}
	if(pre[t]==-1)return 0;
	return 1;
}
void fun(int s,int t,int &flow,int &cost){
	flow=cost=0;
	while(spfa(s,t)){
		int MIN=INF;
		for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
			if(MIN>edge[i].cap)MIN=edge[i].cap;
		for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
			edge[i].cap-=MIN,edge[i^1].cap+=MIN,cost+=edge[i].cost*MIN;
		flow+=MIN;
	}
}
int a[70][70];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int m,k;
	 while(~scanf("%d%d",&m,&k)){
		 for(int i=1;i<=m;i++)
			 for(int j=1;j<=m;j++)
				 scanf("%d",&a[i][j]);
		 memset(head,-1,sizeof(head));tol=0;
		 for(int i=1;i<=m;i++)
			 for(int j=1;j<=m;j++){
				 int tt=(i-1)*m+j;
				 addedge(tt,tt+m*m,1,-a[i][j]);
				 addedge(tt,tt+m*m,INF,0);
				 if(i<m)addedge(tt+m*m,tt+m,k,0);
				 if(j<m)addedge(tt+m*m,tt+1,k,0);
			 }
		 addedge(0,1,k,0);
		 addedge(2*m*m,2*m*m+1,k,0);
		 int flow,cost;
		 n=2*m*m+10;
		 fun(0,2*m*m+1,flow,cost);
		 cout<<-cost<<endl;
	 }
     return 0;
}

拆点，入点向出点连流量为1，费用为权值的相反数，每一个点向右方，下方连流量为无穷大，费用为0的边，添加1，m*m流量为1的边，表示可以算两次。

跑费用流。

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/17 9:42:51
File Name :6.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 100000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=800000;
const int maxm=5001000;
struct Edge{
    int next,to,cap,cost;
    Edge(int _next=0,int _to=0,int _cap=0,int _cost=0){
        next=_next;to=_to;cap=_cap;cost=_cost;
    }
}edge[maxm];
int head[maxn],vis[maxn],pre[maxn],dis[maxn],n,tol;
void addedge(int u,int v,int cap,int cost){
    edge[tol]=Edge(head[u],v,cap,cost);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0,-cost);head[v]=tol++;
}
bool spfa(int s,int t){
    queue<int> q;
    for(int i=0;i<=n;i++)
        dis[i]=INF,vis[i]=0,pre[i]=-1;
    dis[s]=0;vis[s]=1;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(edge[i].cap&&dis[v]>dis[u]+edge[i].cost){
                dis[v]=dis[u]+edge[i].cost;
                pre[v]=i;
                if(!vis[v])vis[v]=1,q.push(v);
            }
        }
    }
    if(pre[t]==-1)return 0;
    return 1;
}
void fun(int s,int t,int &flow,int &cost){
    flow=cost=0;
    while(spfa(s,t)){
        int MIN=INF;
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
            if(MIN>edge[i].cap)MIN=edge[i].cap;
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
            edge[i].cap-=MIN,edge[i^1].cap+=MIN,cost+=edge[i].cost*MIN;
        flow+=MIN;
    }
}
int a[700][700];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int m;
     while(~scanf("%d",&m)){
         for(int i=1;i<=m;i++)
             for(int j=1;j<=m;j++)
                 scanf("%d",&a[i][j]);
         memset(head,-1,sizeof(head));tol=0;
         for(int i=1;i<=m;i++)
             for(int j=1;j<=m;j++){
                 int tt=(i-1)*m+j;
                 addedge(tt,tt+m*m,1,-a[i][j]);
                 if(i<m)addedge(tt+m*m,tt+m,INF,0);
                 if(j<m)addedge(tt+m*m,tt+1,INF,0);
             }
         addedge(1,m*m+1,1,0);
         addedge(m*m,2*m*m,1,0);
         int flow,cost;
         n=2*m*m+10;
         fun(1,2*m*m,flow,cost);
         cout<<-cost<<endl;
     }
     return 0;
}