题解 P4009 【汽车加油行驶问题】

Adove · 2018-03-21 20:50:23 · 题解

本题适合作分层图最短路的模板题（当然你也可以用来练最小费用最大流。

分层图大概长这样↓（这是费用流建图，最短路去掉源汇点即可）

图分为k+1层，箭头所指可以直达，蓝线自下而上需要付费（即最短路边权，费用流费用），黄线自高层连到基层需要付费（同上），最后在每一层的右下扫一遍取最小值即可。

上代码↓

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF=2e9;

int n,k,p,b,c,np;
int h[350005],ln[350005],q[900005];
bool vis[350005],oil;
struct rpg{
    int li,nx,ln;
}a[900005];

void add(int x1,int y1,int z1,int x2,int y2,int z2,int ln){
    int ls=n*n*(z1-1)+(x1-1)*n+y1,nx=n*n*(z2-1)+(x2-1)*n+y2;
    a[++np]=(rpg){h[ls],nx,ln};
    h[ls]=np;
}

void spfa(){
    for(int i=1;i<=n*n*(k+1);++i) ln[i]=INF;
    int hd=1,tl=1;
    q[hd]=1;
    ln[1]=0;
    while(hd<=tl){
        int nw=q[hd++];
        vis[nw]=0;
        for(int i=h[nw];i;i=a[i].li){
            if(ln[a[i].nx]>ln[nw]+a[i].ln){
                ln[a[i].nx]=ln[nw]+a[i].ln;
                if(!vis[a[i].nx]){
                    vis[a[i].nx]=1;
                    q[++tl]=a[i].nx;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d%d",&n,&k,&p,&b,&c);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",&oil);
            for(int l=1;l<=k;++l){
                add(i,j,l,i,j,l+1,0);
            }
            if(oil){
                for(int l=2;l<=k+1;++l){
                    add(i,j,l,i,j,1,p);
                }
                if(i<n) add(i,j,1,i+1,j,2,0);
                if(j<n) add(i,j,1,i,j+1,2,0);
                if(i>1) add(i,j,1,i-1,j,2,b);
                if(j>1) add(i,j,1,i,j-1,2,b);
            }else{
                for(int l=1;l<=k;++l){
                    if(i<n) add(i,j,l,i+1,j,l+1,0);
                    if(j<n) add(i,j,l,i,j+1,l+1,0);
                    if(i>1) add(i,j,l,i-1,j,l+1,b);
                    if(j>1) add(i,j,l,i,j-1,l+1,b);
                }for(int l=2;l<=k+1;++l){
                    add(i,j,l,i,j,1,p+c);
                }
            }
        }
    }spfa();
    int ans=INF;
    for(int i=1;i<=k+1;++i) ans=min(ans,ln[n*n*i]);
    printf("%d\n",ans);
    return 0;
}