CODEVS_1227 方格取数2 网络流最小费用流拆点

原题链接：http://codevs.cn/problem/1227/

题目描述 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

数据范围及提示 Data Size & Hint

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

这道题是道很裸的拆点最小费用流，每个点拆开后建两条边，一条费用是-a[i][j]，容量为1，另一条费用是0，容量为INF。其余的都用费用为0，容量为INF的边连接，每个点连到汇点。最后最小费用流的相反数就是答案。详见代码：

#include<iostream>

#include<vector>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<set>

#define MAX_N 55

#define MAX_V 6000

#define INF 1008611

using namespace std;

int K,N;

int a[MAX_N][MAX_N];

struct edge{int to,cap,cost,rev;};

int V=0;

vector<edge> G[MAX_V];

int dist[MAX_V];

int prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost)

{

    G[from].push_back((edge){to,cap,cost,G[to].size()});

    G[to].push_back((edge){from,0,-cost,G[from].size()-1});

}

char cc;

int min_cost_flow(int s,int t,int f)

{

    int res=0;

    while(f>0)

    {

        fill(dist,dist+V,INF);

        dist[s]=0;

        bool update=1;

        while(update)

        {

            update=0;

            for(int v=0;v<V;v++)

            {

                if(dist[v]==INF)continue;

                for(int i=0;i<G[v].size();i++)

                {

                    edge &e=G[v][i];

                    if(e.cap>0&&dist[e.to]>dist[v]+e.cost)

                    {

                        //cout<<"*"<<endl;

                        dist[e.to]=dist[v]+e.cost;

                        prevv[e.to]=v;

                        preve[e.to]=i;

                        update=1;

                    }

                }

            }

        }

        if(dist[t]==INF)

            return -1;

        int d=f;

        for(int v=t;v!=s;v=prevv[v])

            d=min(d,G[prevv[v]][preve[v]].cap);

        f-=d;

        res+=d*dist[t];

        for(int v=t;v!=s;v=prevv[v])

        {

            edge &e=G[prevv[v]][preve[v]];

            e.cap-=d;

            G[v][e.rev].cap+=d;

        }

    }

    return res;

}

int main()

{

    cin>>N>>K;

    for(int i=0;i<N;i++)

        for(int j=0;j<N;j++)

            cin>>a[i][j];

    V=N*N*2+1;

    for(int i=0;i<N;i++)

        for(int j=0;j<N;j++)

        {

            int v=(i*N+j)*2;

            int u=v+1;

            add_edge(v,u,1,-a[i][j]);

            add_edge(v,u,INF,0);

            if(i!=N-1)

                add_edge(u,((i+1)*N+j)*2,INF,0);

            if(j!=N-1)

                add_edge(u,u+1,INF,0);

            add_edge(u,V-1,INF,0);

        }

    cout<<-min_cost_flow(0,V-1,K)<<endl;

    return 0;

}

巴特西

CODEVS_1227 方格取数2 网络流最小费用流拆点

最新文章

热门文章

巴特西

CODEVS_1227 方格取数2 网络流 最小费用流 拆点

最新文章

热门文章

CODEVS_1227 方格取数2 网络流最小费用流拆点