最小费用最大流。
建图方式如图所示
然后就是费用流的模板~~
把最小费用转化成最大费用，做法一样。
还有一种做法，就是把所有的边的费用取负，然后去最小费用，然后去负值就好。‘
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define INF 99999999
#define maxn 5050
#define LL long long
struct list
{
int l;
int r;
int v;
int f;
int next;
}node[1000001];
int num;
int head[1000001];
int pre[maxn];
int n,k;
int st,ed;
LL ans;
int ns;
void add(int l,int r,int v,int f)
{
node[num].l=l;
node[num].r=r;
node[num].v=v;
node[num].f=f;
node[num].next=head[l];
head[l]=num++;
node[num].l=r;
node[num].r=l;
node[num].v=-v;
node[num].f=0;
node[num].next=head[r];
head[r]=num++;
}
int bfs()
{
int visit[maxn];
int dist[maxn];
int i;
for(i=0;i<=ns;i++)dist[i]=-1;
memset(visit,0,sizeof(visit));
memset(pre,-1,sizeof(pre));
queue<int >q;
q.push(0);
dist[0]=0;
visit[0]=1;
while(!q.empty())
{
int e=q.front();
q.pop();
visit[e]=0;
for(i=head[e];i!=-1;i=node[i].next)
{
int r=node[i].r;
if(dist[r]<dist[e]+node[i].v&&node[i].f>0)
{
pre[r]=i;
dist[r]=dist[e]+node[i].v;
if(!visit[r])
{
q.push(r);
visit[r]=1;
}
}
}
}
if(dist[ns]==-1)return 0;
return 1;
}
void change()
{
int minx,i;
minx=INF;
for(i=pre[ns];node[i].l!=0;i=pre[node[i].l])
{
minx=min(minx,node[i].f);
}
for(i=pre[ns];node[i].l!=0;i=pre[node[i].l])
{
node[i].f-=minx;
node[i^1].f+=minx;
ans+=minx*node[i].v;
}
}
int main()
{
int i,j;
int ll,rr;
while(~scanf("%d%d",&n,&k))
{
memset(head,-1,sizeof(head));
num=0;
int a;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a);
ll=(i-1)*n+j;
rr=ll+n*n;
add(ll,rr,a,1);
add(ll,rr,0,k-1);
if(j<n)
{
ll=(i-1)*n+j+n*n;
rr=(i-1)*n+j+1;
add(ll,rr,0,k);
}
if(i<n)
{
ll=(i-1)*n+j+n*n;
rr=i*n+j;
add(ll,rr,0,k);
}
}
}
ll=n*n+n*n;
rr=ll+1;
ns=rr;
ans=0;
add(0,1,0,k);
add(ll,rr,0,k);
while(bfs())change();
cout<<ans<<endl;
}
return 0;
}
poj-3422-Kaka's Matrix Travels-最小费用最大流
原文：http://blog.csdn.net/rowanhaoa/article/details/18951471