【poj3422】 Kaka's Matrix Travels

时间：2021-09-10 14:04:30

http://poj.org/problem?id=3422 (题目链接)

题意

　　N*N的方格，每个格子中有一个数，寻找从(1,1)走到(N,N)的K条路径，使得取到的数的和最大。

Solution

　　同【codevs1277】 方格取数

代码

// poj3422

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

struct edge {int from,to,next,c,w;}e[maxn<<1];

int head[maxn],dis[maxn],vis[maxn],f[maxn],p[maxn];

int cnt=1,n,m,es,et,K;

void link(int u,int v,int c,int w) {

    e[++cnt]=(edge){u,v,head[u],c,w};head[u]=cnt;

    e[++cnt]=(edge){v,u,head[v],-c,0};head[v]=cnt;

}

int SPFA() {

    queue<int> q;

    memset(dis,-1,sizeof(dis));

    q.push(es);dis[es]=0;f[es]=inf;

    while (!q.empty()) {

        int x=q.front();q.pop();

        vis[x]=0;

        for (int i=head[x];i;i=e[i].next) if (e[i].w && dis[e[i].to]<dis[x]+e[i].c) {

                dis[e[i].to]=dis[x]+e[i].c;

                f[e[i].to]=min(f[x],e[i].w);

                p[e[i].to]=i;

                if (!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;

            }

    }

    if (dis[et]==-1) return 0;

    for (int i=p[et];i;i=p[e[i].from]) e[i].w-=f[et],e[i^1].w+=f[et];

    return f[et]*dis[et];

}

int EK() {

    int ans=0;

    for (int i=1;i<=K;i++) ans+=SPFA();

    return ans;

}

int main() {

    scanf("%d%d",&n,&K);

    es=n*n+1;et=n*n+2;

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

        for (int x,y,w,j=1;j<=n;j++) {

            scanf("%d",&w);

            x=(i-1)*n+j;y=x+n*n+2;

            link(x,y,w,1);link(x,y,0,inf);

            if (i<n) link(y,x+n,0,inf);

            if (j<n) link(y,x+1,0,inf);

        }

    link(es,1,0,inf);link(n*n+n*n+2,et,0,inf);

    printf("%d",EK());

    return 0;

}

　　

相关文章