poj 3422 洛谷P2045 K取方格数（方格取数加强版）

Description：

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

Input：

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

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

Output：

一个数,为最大和

思路：仍旧是拆点因为每个点都有一个限制K和一个价值V 所以将一个点拆成两个点，对相邻的点连两条边，一条费用为V，限制为1，一条费用为0，限制为K - 1。然后跑个最大费用最大流即可

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

const int N = , M = ;

int d[N], incf[N], pre[N], n, k, s, t, maxflow, ans;

bool vis[N];

int head[N],now;

struct edges{

    int to,next,lim,w;

}edge[N<<];

void add(int x,int y,int z,int c){

    edge[++now] = {y,head[x],z,c};

    head[x] = now;

    edge[++now] = {x,head[y],,-c};

    head[y] = now;

}

int id(int i,int j,int k){    return (i - )*n + j + k * n * n;}

bool spfa(){

    queue<int> q;

    memset(d,0xcf,sizeof(d));

    memset(vis,,sizeof(vis));

    q.push(s); d[s] = ; vis[s] = ;

    incf[s] = 1e9;

    while(!q.empty()){

        int x = q.front(); vis[x] = ; q.pop();

        for(int i = head[x]; i; i = edge[i].next){

            int v = edge[i].to;

            if(!edge[i].lim) continue;

            if(d[v] < d[x] + edge[i].w){

                d[v] = d[x] + edge[i].w;

                incf[v] = min(incf[x], edge[i].lim);

                pre[v] = i;

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

            }

        }

    }

    if(d[t] == 0xcfcfcfcf) return ;

    return ;

}

void update(){

    int x = t;

    while(x != s){

        int i = pre[x];

        edge[i].lim -= incf[t];

        edge[i ^ ].lim += incf[t];

        x = edge[i ^ ].to;

    }

    maxflow += incf[t];

    ans += d[t] * incf[t];

}

int main(){

    ios::sync_with_stdio(false);

    cin>>n>>k;

    s = , t = *n*n;

    now = ;

    int x;

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

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

        cin>>x;

        add(id(i,j,),id(i,j,),,x);

        add(id(i,j,),id(i,j,),k - ,);

        if(j < n) add(id(i,j,),id(i,j+,),k,);

        if(i < n) add(id(i,j,),id(i+,j,),k,);

      }

    while(spfa())

     update();

    cout<<ans<<endl;

    return ;

}

巴特西

poj 3422 洛谷P2045 K取方格数（方格取数加强版）

最新文章

热门文章