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

相信一定有一些人一看到N<=50就想搜索（233……），但是显然TLE。

那么对于K<=10，我记得当k<=2时,貌似用DP也能做。

这题的坑就在于“加强版”，其实这题是个图论。

再看看，不难想到这是网络流“最大流最大消费”，再看到aij<=1000，便可以将每个数取负数，就最小消费流即可。

怎么建图，是网络流中的难点。

因为每个点只能去一次，所以拆成两点，这两点之间有两条路，一条只能走一次（流量为1），但可以取到数（费用为-aij）

另一点最多能走k次，取不到数。

有人喜欢建超级源点和汇点（因为只取k次），其实不用如此。

我们从1,1点出发SPFAk次即可，注意如果有一次到不了终点直接结束！

OK，就这样AC了。注意点的位置，我用的是pos（i,j）=(i-1)*n+j，比较方便。

AC代码如下：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define pos(i,j)  (i-1)*n+j
using namespace std;
const int N=2500+5;
const int M=N*2*10;
struct p
{
    int to,w,cost,nxt;
}e[M];
int h[N<<1],dis[N<<1],pre[N<<1];
bool inq[N<<1];
int x,num,n,k,cnt;
void add(int u,int v,int ds,int cst)
{
    e[cnt].nxt=h[u];
    e[cnt].to=v;
    e[cnt].w=ds;
    e[cnt].cost=cst;
    h[u]=cnt;
    cnt++;
    e[cnt].nxt=h[v];
    e[cnt].to=u;
    e[cnt].w=0;
    e[cnt].cost=-cst;
    h[v]=cnt;
    cnt++;
}
int solve()
{
    int ans=0;
    while(k--)
    {
        memset(dis,0x3f,sizeof(dis));
        memset(pre,-1,sizeof(pre));
        queue<int>q;
        q.push(1);
        dis[1]=1;
        while(!q.empty())
        {
            int now=q.front();
            q.pop();inq[now]=0;
            for(int i=h[now];i!=-1;i=e[i].nxt)
              if(e[i].w&&dis[e[i].to]>dis[now]+e[i].cost)
              {
                  dis[e[i].to]=dis[now]+e[i].cost;
                  pre[e[i].to]=i;
                  if(!inq[e[i].to]) q.push(e[i].to),inq[e[i].to]=1;
              }
        }
        if(pre[n*n+N]==-1) return -ans;
        int mx=1,j=n*n+N;
        while(pre[j]!=-1)
        {
            mx=min(mx,e[pre[j]].w);
            j=e[pre[j]^1].to;
        }
        j=n*n+N;
        while(pre[j]!=-1)
        {
            ans+=e[pre[j]].cost*mx;
            e[pre[j]].w-=mx;
            e[pre[j]^1].w+=mx;
            j=e[pre[j]^1].to;
        }
    }
    return -ans;
}
int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
    scanf("%d",&x);
    num=pos(i,j);
    add(num,num+N,1,-x);add(num,num+N,k,0);
    if(i!=n) add(num+N,pos(i+1,j),k,0);
    if(j!=n) add(num+N,pos(i,j+1),k,0);
    }
    printf("%d",solve());
    return 0;
}

posted on 2018-01-30 15:00 Alex&leaves 阅读(…) 评论(…) 编辑收藏

本文链接：https://www.cnblogs.com/Alex-leaves/p/8384998.html

P2045 方格取数加强版