将每个点拆分成原点A与伪点B，A->B有两条单向路(邻接表实现时需要建立一条反向的空边，并保证环路费用和为0)，一条残留容量为1，费用为本身的负值(便于计算最短路)，另一条残留容量+∞，费用为0(保证可以多次通过该点，但费用只计算一次)。
另外伪点B与原点右侧与下方的点有一条单向路(邻接表实现需要建立反向空边)，残留容量为+∞，费用为0。源点0到点1有一条单向路，残留容量为K(可以通过K次)，最后一个点的伪点2*n*n与汇点2*n*n+1有一条单向边，残留容量为K，两条边的费用都为0。
构图成功后，走一次最小费用最大流即可。
//最小费用最大流问题-拆点
//Time:47Ms Memory:624K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 55
#define MAXN 5005
#define INF 0x3f3f3f3f
struct Edge{
int u,v,r,w,next;
Edge(){}
Edge(int U,int V,int R,int W,int N):u(U),v(V),r(R),w(W),next(N){}
}e[MAXN*8];
int n,k;
int s,t;
int h[MAXN],le;
int m[MAX][MAX];
int pre[MAXN];
int cost[MAXN];
bool vis[MAXN];
void add(int u,int v,int r,int w)
{
e[le] = Edge(u,v,r,w,h[u]); h[u] = le++;
e[le] = Edge(v,u,0,-w,h[v]); h[v] = le++;
}
void build()
{
add(s, 1, k, 0);
add(2*n*n, t, k, 0);
for(int i = 1; i <= n*n; i++)
{
add(i, n*n+i, 1, -m[(i - 1)/n + 1][(i - 1)%n + 1]);
add(i, n*n+i, k, 0);
if(i % n) add(i+n*n, i+1, INF, 0);
if(i <= n*(n-1)) add(i+n*n, i+n, INF, 0);
}
}
bool spfa()
{
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
memset(cost,INF,sizeof(cost));
queue<int> q;
q.push(s);
cost[s] = 0; vis[s] = true;
while(!q.empty()){
int cur = q.front();
q.pop(); vis[cur] = false;
for(int i = h[cur]; i != -1; i = e[i].next)
{
int v = e[i].v;
if(e[i].r && cost[v] > cost[cur] + e[i].w){
cost[v] = cost[cur] + e[i].w;
pre[v] = i;
if(!vis[v]){
vis[v] = true; q.push(v);
}
}
}
}
return cost[t] == INF? false: true;
}
int maxcostflow()
{
int maxFlow = 0;
while(spfa()){ //增广路
int mind = INF;
for(int i = pre[t]; i != -1; i = pre[e[i].u])
mind = min(mind, e[i].r);
for(int i = pre[t]; i != -1; i = pre[e[i].u])
{
e[i].r -= mind;
e[i^1].r += mind;
}
maxFlow += mind*cost[t];
}
return maxFlow;
}
int main()
{
//freopen("in.txt", "r", stdin);
memset(h, -1, sizeof(h));
scanf("%d%d", &n,&k);
s = 0; t = 2*n*n+1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &m[i][j]);
build();
printf("%d\n", -maxcostflow());
return 0;
}
ACM/ICPC 之 卡卡的矩阵旅行-最小费用最大流(可做模板)(POJ3422)
原文：http://www.cnblogs.com/Inkblots/p/5719179.html