P2045 方格取数加强版

题目描述

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入输出格式

输入格式：

第一行两个数n,k（1<=n<=50, 0<=k<=10）

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式：

一个数,为最大和

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

每个格子中的数不超过1000

//Pro:方格取数加强版 

//这个模型大概是个挺经典的问题吧
//建模：
//超级源点连(1,1)，超级汇点连(n,n)，容量为k，费用为0，表示可以走k次 
//将(i,j)拆点，入点和出点间连两条边，一条容量为1，花费为点的值，表示这个点仅可以取一次。
//                                    一条容量INF，花费为0，表示这个点可以经过无数次 
//然后就跑最小费用最大流就可以了
//(其实是最大费用最大流) 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

inline int read()
{
    char c=getchar();int num=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        num=num*10+c-'0';
    return num;
}

const int N=1e5+5;
const int INF=0x3f3f3f3f;

int n,k,S,T,ans;
int map[55][55];
int head[N],num_edge;
struct Edge
{
    int v,flow,cost,nxt;
}edge[N];

void add_edge(int u,int v,int flow,int cost)
{
    edge[++num_edge].v=v;
    edge[num_edge].flow=flow;
    edge[num_edge].cost=cost;
    edge[num_edge].nxt=head[u];
    head[u]=num_edge;
}

queue<int> que;
int vis[N],tim,now;
int dis[N];
bool spfa()
{
    memset(dis,-1,sizeof(dis));
    ++tim;
    que.push(S);
    dis[S]=0;
    while(!que.empty())
    {
        now=que.front(),que.pop();
        for(int i=head[now],v;i;i=edge[i].nxt)
        {
            if(!edge[i].flow)
                continue;
            v=edge[i].v;
            if(dis[v]<dis[now]+edge[i].cost)
            {
                dis[v]=dis[now]+edge[i].cost;
                if(vis[v]!=tim)
                {
                    vis[v]=tim;
                    que.push(v);
                }
            }
        }
        vis[now]=0;
    }
    return dis[T]!=dis[T+1];
}

int dfs(int now,int flow)
{
    if(now==T||!flow)
        return flow;
    vis[now]=tim;
    int outflow=0,tmp;
    for(int i=head[now],v;i;i=edge[i].nxt)
    {
        if(!edge[i].flow)
            continue;
        v=edge[i].v;
        if(vis[v]==tim||dis[v]!=dis[now]+edge[i].cost)
            continue;
        tmp=dfs(v,min(flow,edge[i].flow));
        edge[i].flow-=tmp;
        edge[i^1].flow+=tmp;
        flow-=tmp;
        outflow+=tmp;
        ans+=tmp*edge[i].cost;
        if(!flow)
            break;
    }
    dis[now]=0;
    return outflow;
}

#define A n*(i-1)+j

int main()
{
    num_edge=1;
    n=read(),k=read();
    T=n*n*2+1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            map[i][j]=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            add_edge(A,A+n*n,1,map[i][j]);
            add_edge(A+n*n,A,0,-map[i][j]);
            add_edge(A,A+n*n,INF,0);
            add_edge(A+n*n,A,0,0);
            if(i<n)
            {
                add_edge(A+n*n,A+n,INF,0);
                add_edge(A+n,A+n*n,0,0);
            }
            if(j<n)
            {
                add_edge(A+n*n,A+1,INF,0);
                add_edge(A+1,A+n*n,0,0);
            }
        }
    add_edge(S,1,k,0);
    add_edge(1,S,0,0);
    add_edge(n*n*2,T,k,0);
    add_edge(T,n*n*2,0,0);
    while(spfa())
    {
        ++tim;
        dfs(S,INF);
    }
    printf("%d",ans);
    return 0;
}