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

hbxblog 2021-08-20 原文

题目链接

戳我

\(Solution\)

网络流是什么?可以吃吗?

这道题明显不需要网络流啊,直接暴力\(bfs\)即可

令f[x][y][k]表示在\(x,y\)时还剩下\(k\)步的最小花费

然后向四周扩展即可

\(Code\)

#include<bits/stdc++.h>
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<\'0\'||c>\'9\') f=(c==\'-\')?-1:1,c=getchar();
    while(c>=\'0\'&&c<=\'9\') x=x*10+c-48,c=getchar();
    return f*x;
}
int f[111][111][21];
struct node {
    int x,y,k,v;
};
int fx[6]={0,0,0,-1,1};
int fy[6]={0,1,-1,0,0};
int fv[6],A,C,n,K,bj[111][111];
queue<node> q;
void bfs(){
    q.push((node){1,1,K,0});
    memset(f,127,sizeof(f));
    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.v>=f[now.x][now.y][now.k]) continue;
        f[now.x][now.y][now.k]=now.v;
        for(int i=1;i<=4;i++) {
            int x=now.x+fx[i],y=now.y+fy[i];
            if(x<1||y<1||x>n||y>n) continue;
            if(bj[now.x][now.y]) q.push((node){x,y,K-1,now.v+A+fv[i]});
            else if(!now.k) q.push((node){x,y,K-1,now.v+C+A+fv[i]});
            else q.push((node){x,y,now.k-1,now.v+fv[i]}); 
        }
    }
}
int main(){
    n=read(),K=read(),A=read(),fv[2]=fv[3]=read(),C=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            bj[i][j]=read();
    bfs();
    int minx=2147483547;
    for(int i=0;i<=K;i++)
        minx=min(minx,f[n][n][i]);
    cout<<minx<<endl;
    return 0;
}