学步园

题目链接:   poj 3422

题目大意:   给出NxN的数字矩阵，左上角走到右下角(只能向右或向下走)，sum记录走过点值的和

                  走过的点值置为0，问走K次，求sum的最大值

解题思路:   开始想到的是K次最长路，结果WA了

                  因为每次走最长路会导致下次走的时候不是最优解

                  建立费用流模型，把每个顶点T，分成两个顶点T和T''

                  因为要限制每个顶点的值只加一次，T->T''容量为1，费用为T的值：

                  1.建立超级源点，源点指向顶点T1，容量为K，费用0

                  2.建立超级汇点，顶点T(2*n)指向汇点，容量为K，费用为0

                  3.每个顶点拆分为两个点，加两条边 (Ti指向Ti''，容量为1，费用为T的值)

                     (Ti指向Ti''，容量为K，费用为0)

                  4.若能从T1走到T2，则T1''连T2，容量为K，费用为0

                  然后求一次最小费用最大流就是最终结果

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 5100
#define INF 0x3f3f3f3f
#define Min(a,b) (a<b?a:b)
int S,E,vis[MAX],pre[MAX],Index,dis[MAX],path[MAX],que[2000000],Fi[MAX*100];
int Fx[2][2]={{1,0},{0,1}};

struct snode{
    int r,to,c,w,next;
}Edge[MAX*100];

void Add_edge(int a,int b,int c,int d)
{
    d=-d;       //等价于负边求最小费用流
    Edge[Index].to=b,Edge[Index].c=c,Edge[Index].w=d;
    Edge[Index].next=pre[a],Edge[Index].r=Index+1,pre[a]=Index++;

    Edge[Index].to=a,Edge[Index].c=0,Edge[Index].w=-d;            //反向边C为0,费用为-d
    Edge[Index].next=pre[b],Edge[Index].r=Index-1,pre[b]=Index++;
}

bool BFS()
{
    int i,s,e,v1,v2;
    memset(vis,0,sizeof(vis));
    memset(path,-1,sizeof(path));
    memset(dis,INF,sizeof(dis));
    s=e=0;
    que[s++]=S; vis[S]=1; dis[S]=0;
    while(s!=e)
    {
        v1=que[e++];
        vis[v1]=0;
        for(i=pre[v1];i!=-1;i=Edge[i].next)
        {
            v2=Edge[i].to;
            if(Edge[i].c&&(dis[v2]==INF||dis[v2]>dis[v1]+Edge[i].w))  //<是最大费用流,>是最小费用流
            {
                dis[v2]=dis[v1]+Edge[i].w;
                path[v2]=v1,Fi[v2]=i;
                if(!vis[v2])
                {
                    vis[v2]=1;
                    que[s++]=v2;
                }
            }
        }
    }
    if(dis[E]==INF)
        return false;
    return true;
}

int Find()
{
    int i,sum=0,MIN=INF;
    for(i=E;i!=-1;i=path[i])
    {
        if(path[i]!=-1)
            MIN=Min(MIN,Edge[Fi[i]].c);
    }
    for(i=E;i!=-1;i=path[i])
    {
        if(path[i]!=-1)
        {
            Edge[Fi[i]].c-=MIN;
            Edge[Edge[Fi[i]].r].c+=MIN;
            sum=sum+(Edge[Fi[i]].w*MIN);
        }
    }
    return sum;
}

int Solve()
{
    int sum=0;
    while(BFS())
        sum+=Find();
    return sum;
}

int main()
{
    int i,j,n,k,a,b,c,d,num[53][53];
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        Index=0;
        memset(pre,-1,sizeof(pre));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%d",&num[i][j]);
        S=0,E=n*n*2+1;
        Add_edge(S,1,k,0);    //左边
        Add_edge(E-1,E,k,0);  //右边
        int v1,v2,j1,x,y;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                v1=(i-1)*n+j;
                Add_edge(v1*2-1,v1*2,1,num[i][j]);   //分点边1
                Add_edge(v1*2-1,v1*2,k,0);           //分点边2
                for(j1=0;j1<2;j1++)
                {
                    x=i+Fx[j1][0],y=j+Fx[j1][1];
                    if(x>=1&&x<=n&&y>=1&&y<=n)
                    {
                        v2=(x-1)*n+y;
                        Add_edge(v1*2,v2*2-1,k,0);   //各点间
                    }
                }
            }
        }
        printf("%d\n",-Solve());
    }
    return 0;
}