Codevs 1227 方格取数 2(费用流)

1227 方格取数 2

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

查看运行结果

题目描述 Description

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

输入描述 Input Description

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

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

输出描述 Output Description

一个数,为最大和

样例输入 Sample Input

3 1

1 2 3

0 2 1

1 4 2

样例输出 Sample Output

11

数据范围及提示 Data Size & Hint

1<=n<=50, 0<=k<=10

分类标签 Tags

网络流费用流图论

/*

拆点+费用流.

自己yy不对然后看的题解orz.

考虑两个东西.

一是计算答案贡献并保证贡献只计算一次.

二是使图连通.

通过一我们很容易想到拆点后建一条流量为1费用为格子贡献的边.

通过二拆点后建一条流量为k-1费用为0的边.

然后把(i,j)与(i-1,j)和(i,j-1)连接起来.

*/

#include<iostream>

#include<cstdio>

#include<queue>

#define MAXN 10010

#define INF 1e9

using namespace std;

int n,k,ans,cut=1,tot,S,T,head[MAXN],g[51][51],dis[MAXN],b[MAXN],fa[MAXN];

struct data{int u,v,next,c,f;}e[MAXN*2];

queue<int>q;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int c,int f)

{

    e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].f=f;e[cut].next=head[u];head[u]=cut;

    e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].f=-f;e[cut].next=head[v];head[v]=cut;

}

bool bfs(int t)

{

    q.push(S);

    for(int i=0;i<=T;i++) dis[i]=-INF;dis[S]=0;

    while(!q.empty())

    {

        int u=q.front();q.pop();b[u]=0;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]<dis[u]+e[i].f&&e[i].c)

            {

                dis[v]=dis[u]+e[i].f,fa[v]=i;

                if(b[v]!=t) b[v]=t,q.push(v);

            }

        }

    }

    return dis[T]!=-INF;

}

void mincost()

{

    int t=1;

    while(bfs(t))

    {

        int tmp=fa[T],x=INF;

        while(tmp) x=min(x,e[tmp].c),tmp=fa[e[tmp].u];

        tmp=fa[T];

        while(tmp)

        {

            e[tmp].c-=x;

            e[tmp^1].c+=x;

            tmp=fa[e[tmp].u];

        }

        ans+=dis[T]*x;

    }

    return ;

}

int main()

{

    n=read(),k=read();S=0,T=2*n*n+1;

    for(int i=1;i<=n;i++)

      for(int j=1;j<=n;j++)

        g[i][j]=read(),tot+=g[i][j];

    add(0,1,k,0),add(2*n*n,T,k,0);

    for(int i=1;i<=n;i++)

      for(int j=1;j<=n;j++)

        add((i-1)*n+j,(i-1)*n+j+n*n,1,g[i][j]),

        add((i-1)*n+j,(i-1)*n+j+n*n,k-1,0);

    for(int i=1;i<=n;i++)

      for(int j=1;j<=n;j++)

      {

        if(i!=n) add((i-1)*n+j+n*n,i*n+j,k,0);

        if(j!=n) add((i-1)*n+j+n*n,(i-1)*n+j+1,k,0);

      }

    mincost();

    printf("%d",ans);

    return 0;

}

巴特西

Codevs 1227 方格取数 2(费用流)

最新文章

热门文章