【网络流24题】汽车加油行驶问题

作者: MayFlyyh 分类: 网络流 发布时间: 2018-06-29 13:21 ė 6 1条评论

【网络流24题】汽车加油行驶问题

给定一个N×N 的方形网格,设其左上角为起点◎,坐标 (1,1),X轴向右为正,Y 轴向下为正,每个方格边长为 11 ,如图所示。

image

一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 (N,N)(N,N) 。

在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

汽车只能沿网格边行驶,装满油后能行驶 K 条网格边。出发时汽车已装满油,在起点与终点处不设油库。

汽车经过一条网格边时,若其 X 坐标或 Y 坐标减小,则应付费用 BB ,否则免付费用。

汽车在行驶过程中遇油库则应加满油并付加油费用 A 。

在需要时可在网格点处增设油库,并付增设油库费用 C (不含加油费用 AA )。

N,K,A,B,C 均为正整数, 且满足约束: 2≤N≤100,2≤K≤10 。

设计一个算法,求出汽车从起点出发到达终点所付的最小费用。


分层图最短路(费用流),设dis[N][K]表示当前状态在N位置,不加油还能跑K步,按照题目条件转移即可

要注意貌似到油站可以加油也可以不加油。。。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
const int N = 110;
int dis[N][N][15];
int map[N][N];
int n,k,a,b,c;
int v[N][N][15];
int dx[5]={0,-1,0,1};
int dy[5]={-1,0,1,0};
struct heap {
    int x,y,d,v;
    bool operator < (const heap m) const{
        return v>m.v;
        //if(d!=m.d)
        //return d<m.d;
    }   
};
int main (){
    scanf("%d %d %d %d %d",&n,&k,&a,&b,&c);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",&map[i][j]);
        }
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1][1][k]=0;
    std::priority_queue<heap> q;
    q.push((heap){1,1,k,0});
    int cnt=0;
    while(!q.empty()){
        cnt++;
        heap x=q.top();q.pop();
        if(v[x.x][x.y][x.d])continue;
        v[x.x][x.y][x.d]=1;
        int cost=a;
        if(map[x.x][x.y]==1&&x.d!=k){
            if(dis[x.x][x.y][k]<=dis[x.x][x.y][x.d]+cost) continue;       
            dis[x.x][x.y][k]=dis[x.x][x.y][x.d]+cost;       
            q.push((heap){x.x,x.y,k,dis[x.x][x.y][k]});
            continue;
        }
        cost+=c;
        if(dis[x.x][x.y][k]>dis[x.x][x.y][x.d]+cost){
            dis[x.x][x.y][k]=dis[x.x][x.y][x.d]+cost;
            q.push((heap){x.x,x.y,k,dis[x.x][x.y][k]});
        }
        if(x.d<=0) continue;
        for(int i=0;i<=3;++i){
            int gx=x.x+dx[i];
            int gy=x.y+dy[i];
            if(gx>n||gy>n||gx<1||gy<1) continue;
            int cost=0;
            if(i<=1) cost=b;
            if(x.d!=0&&(dis[gx][gy][x.d-1]>(dis[x.x][x.y][x.d]+cost))){
                dis[gx][gy][x.d-1]=dis[x.x][x.y][x.d]+cost;
                q.push((heap){gx,gy,x.d-1,dis[gx][gy][x.d-1]});
            }
        }

    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;++i){
        ans=std::min(ans,dis[n][n][i]);
        //printf("%d\n",dis[n][n][i]);
    }
   // printf("%d\n",dis[3][1][k]);
    printf("%d",ans);
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/245

一条评论

  1. wjyyy 2018年7月6日 下午9:11 回复

    到油站必须加油啊。。。?

wjyyy进行回复 取消回复

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部