「网络流 24 题」汽车加油行驶问题
题解:对于一个点如果是没有加油站,就有设置加油站或者是直接走,通过调整方向函数将向回走的放在前面,然后就可以收费。
#include <bits/stdc++.h>
const int MAXN = 105,INF = 10000000;
const int fx[] = {-1,0,1,0},fy[] = {0,-1,0,1};
using namespace std;
int n,k,a,b,c,ans;
int oil[MAXN][MAXN],dis[MAXN][MAXN][20];
bool inq[MAXN][MAXN][20];
inline void init()
{
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",&oil[i][j]);
}
struct node{
int x,y,Oil;
};
inline bool check(node car,int i){
if(car.x + fx[i] < 1 || car.x + fx[i] > n) return false;
if(car.y + fy[i] < 1 || car.y + fy[i] > n) return false;
if(car.Oil == 0) return false;
return true;
}
queue<node>Q;
inline void spfa()
{
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
for(int o = 0;o <= k;o++)
dis[i][j][o] = INF;
Q.push((node){1,1,k});dis[1][1][k] = 0;inq[1][1][k] = false;
while(!Q.empty()){
node car = Q.front();Q.pop();inq[car.x][car.y][car.Oil] = false;
int ux = car.x,uy = car.y;
for(int i = 0;i <= 3;i++){
if(check(car,i)){
int vx = ux + fx[i],vy = uy + fy[i];
if(i <= 1){ //pay B
if(oil[vx][vy]) {//pay A
if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + b + a){
dis[vx][vy][k] = dis[ux][uy][car.Oil] + b + a;
if(!inq[vx][vy][k]){
Q.push((node){vx,vy,k});
inq[vx][vy][k] = true;
}
}
}
else {
if(dis[vx][vy][car.Oil-1] > dis[ux][uy][car.Oil] + b && !(vx != n && vy != n && car.Oil - 1 == 0)){
dis[vx][vy][car.Oil-1] = dis[ux][uy][car.Oil] + b;
if(!inq[vx][vy][car.Oil-1]){
Q.push((node){vx,vy,car.Oil-1});
inq[vx][vy][car.Oil-1] = true;
}
}
if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + a + b + c){
dis[vx][vy][k] = dis[ux][uy][car.Oil] + a + b + c;
if(!inq[vx][vy][k]){
Q.push((node){vx,vy,k});
inq[vx][vy][k] = true;
}
}
}
}
else {
if(oil[vx][vy]) {
if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + a){
dis[vx][vy][k] = dis[ux][uy][car.Oil] + a;
if(!inq[vx][vy][k]){
Q.push((node){vx,vy,k});
inq[vx][vy][k] = true;
}
}
}
else {
if(dis[vx][vy][car.Oil-1] > dis[ux][uy][car.Oil] && !(vx != n && vy != n && car.Oil - 1 == 0)){
dis[vx][vy][car.Oil-1] = dis[ux][uy][car.Oil];
if(!inq[vx][vy][car.Oil-1]){
Q.push((node){vx,vy,car.Oil-1});
inq[vx][vy][car.Oil-1] = true;
}
}
if(dis[vx][vy][k] > dis[ux][uy][car.Oil] + a + c){
dis[vx][vy][k] = dis[ux][uy][car.Oil] + a + c;
if(!inq[vx][vy][k]){
Q.push((node){vx,vy,k});
inq[vx][vy][k] = true;
}
}
}
}
}
}
}
}
int main()
{
#ifdef hi_archer
freopen("input.txt", "r", stdin);
#endif
init();
spfa();
ans = INF;
for(int i = 0;i <= k;i++) ans = min(ans,dis[n][n][i]);
printf("%d\n",ans);
return 0;
}