这是一道费用流的题

我们这么建图

把每个格子拆成两个点

上面那个点表示第一次来,下面的表示第二次来

第一次来到第二次来连一条边,权值为-x,流量为1

其他的按走的顺序连边,流量均为0

没了...

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn=4005;
const int inf=99999999;
struct edge
{
    int y;
    int weight;
    int cost;
    edge * next;
    edge * anti;
};
edge * li[maxn];
edge * new_edge()
{
    static edge a[100005];
    static int top=0;
    return &a[top++];
}
edge * inserts(int x,int y,int z,int w)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->cost=w;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y,int z,int w)
{
    edge * t1=inserts(x,y,z,w);
    edge * t2=inserts(y,x,0,-w);
    t1->anti=t2;
    t2->anti=t1;
}
int bfs(int s,int t)
{
    static int que[maxn];
    static int pre[maxn];
    static int dist[maxn];
    static int visit[maxn];
    static edge * path[maxn];
    int front=0,rail=1;
    int i;
    for (i=0;i<=s;i++)
    {
        dist[i]=inf;
        visit[i]=false;
    }
    que[0]=s;
    visit[s]=true;
    dist[s]=0;
    for (;front!=rail;)
    {
        int now=que[front];
        front++;
        if (front==maxn) front=0;
        edge * x;
        for (x=li[now];x!=0;x=x->next)
        {
            if ((x->weight>0)&&(dist[x->y]>dist[now]+x->cost))
            {
                dist[x->y]=dist[now]+x->cost;
                pre[x->y]=now;
                path[x->y]=x;
                if (!visit[x->y])
                {
                    visit[x->y]=true;
                    que[rail++]=x->y;
                    if (rail==maxn) rail=0;
                }
            }
        }
        visit[now]=false;
    }
    if (dist[t]==inf) return inf;
    int mini=inf;
    int now;
    for (now=t;now!=s;now=pre[now])
    {
        mini=min(mini,path[now]->weight);
    }
    for (now=t;now!=s;now=pre[now])
    {
        path[now]->weight-=mini;
        path[now]->anti->weight+=mini;
    }
    return dist[t]*mini;
}
int max_flow_min_cost(int s,int t)
{
    int ans=0;
    for (;;)
    {
        int val=bfs(s,t);
        if (val==inf) return ans;
        ans+=val;
    }
}
int k,n,m;
int code(int x,int y,int z)
{
    return (x*m+y)*2+z;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d%d%d",&k,&m,&n);
    int i;
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            int x;
            scanf("%d",&x);
            insert_edge(code(i,j,0),code(i,j,1),1,-x);
            if (i!=0)
            {
                insert_edge(code(i-1,j,1),code(i,j,0),k,0);
                insert_edge(code(i-1,j,1),code(i,j,1),k,0);
            }
            if (j!=0)
            {
                insert_edge(code(i,j-1,1),code(i,j,0),k,0);
                insert_edge(code(i,j-1,1),code(i,j,1),k,0);
            }
        }
    }
    int s=n*m*2,t=n*m*2+1;
    int ss=n*m*2+2;
    insert_edge(ss,s,k,0);
    insert_edge(s,code(0,0,0),k,0);
    insert_edge(s,code(0,0,1),k,0);
    insert_edge(code(n-1,m-1,0),t,k,0);
    insert_edge(code(n-1,m-1,1),t,k,0);
    printf("%d\n",-max_flow_min_cost(ss,t));
    return 0;
}