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

辰星凌 · 2019-08-28 16:33:54 · 题解

【题解】【网络流24题】汽车加油行驶问题 [P4009] [Loj6223]

传送门：汽车加油行驶问题 [P4009] [Loj6223]

【题目描述】

给出一个 N \times N 的方形网格，设(1,1)为起点，(N,N) 为终点，X 轴向右为正， Y 轴向下为正。

某些地方设有油库，可供汽车加油。汽车行驶应遵守如下规则:

$(2).$ 汽车行驶路线 $X$ 坐标或 $Y$ 坐标每减小 $1$，则应付费用 $B$ ，反之则不用。 $(3).$ 在行驶过程中遇到油库会**强制加满油**并付加油费用 $A$。 $(4).$ 途中可在某点处增设加油站，增设费用为 $C$ $($**不含加油费用** $A$ $)$。求出汽车从起点出发到达终点所付的最小费用。 **【输入】** 第一行五个**正整数** $N,K,A,B,C$。接下来是一个 $N \times N$ 的 $01$ 矩阵，一共 $n$ 行，每行 $n$ 个整数。矩阵的第 $i$ 行第 $j$ 列处的值为 $1$ 表示$(i,j)$ 处有一个加油站,为 $0$ 则无。 **【数据范围】** $100\%$ $2 \leqslant n \leqslant 100,$ $2 \leqslant k \leqslant 10

【分析】

这明明是一道网络瘤的题中なのに，但为啥网络瘤的题解基本没几篇啊 ...

解题思路与这位大佬类似：吾王美如画，本篇题解将针对一些细节进行分析。

首先，应该如何建模呢？

【建模】

俗话说得好啊：网络瘤，网络瘤，网络建模最毒瘤。

注意题目描述中加黑字体部分，如果仔细想想的话，会发现出题人特别良心，为我们去除了很多复杂的情况，建模也方便了许多。

先将题目略微修改一下，原题意不变：一份油可供汽车走一个单位长度，油箱最多可装 K 份油。

把每个坐标分为 $K+1$ 层，用第 $0$ 层表示满油状态，第 $1$ 层表示用掉了 $1$ 份油，第 $2$ 表示用掉了 $2$ 份油 $...$ 第 $K$ 层表示油被用光的状态。 $(2).$ 搞一个**超级源点**和一个**超级汇点**： **超级源点**与第 $0$ 层的 $(1,1)$（满油状态的起点）连一条**流量为** $1$ **费用为** $0$ 的边。每一层的 $(n,n)$（任意状态的终点）与**超级汇点**分别连一条**流量为** $1$ **费用为** $0$ 的边。由于起点与终点重合的情况不存在，所以汽车不可能以满油的状态到达任意一个点，只会以满油的状态从某个点出发（在起点或者加了油之后），因此第 $0$ 层也可以不用连。 $(3).$ 当处理某个点 $(i,j)$ 时，发现这里~~满是汽油味~~（**有加油站**）： **不管油箱里还有多少油**，不知所措的可怜新司机都会被黑心商家**强迫加油**，所以每一层的 $(i,j)$ 都要与第 $0$ 层的 $(i,j)$ 连一条**流量为** $1$ **费用为** $A$的边，与上面所说相同，第 $0$ 层可以不连（实际上自己到自己的边就算连了也不会选）。然后第 $0$ 层的 $(i,j)$ 再与上下左右四个方向坐标的第 $1$ 层分别连一条**流量为** $1$ 的边，当**向左**、**向上**时**费用为** $B$，反之**费用为** $0$ 。 $(4).$ 当处理某个点 $(i,j)$ 时，发现这里~~空气清新~~（**没有加油站**）：可以选择在这里**生成一个加油站**，将第 $K$ 层的 $(i,j)$（空油箱）与第 $0$ 层的 $(i,j)$ 连一条流量为 $1$ 费用为 $A+C$ 的边。然后对于 $k \in [0,K-1]$，将第 $k$ 层的 $(i,j)$ 与上下左右四个方向坐标的第 $k+1$ 层分别连一条**流量为** $1$ 的边，**费用**同上。注意：可以从满油状态出发，所以第 $0$ 层也要连出去。 $Q:$ あの、あの、为什么坐标与坐标连边时流量为 $1$ 鸭？嗯 $...$ 为什么只在油箱为空时才生成加油站捏？还有哇，生成的加油站可能会在下一次到达时再次使用咩？ $A:$ 其实是有点贪心的味道，由于往回走有花费且为**正整数**，所以不会回到已经走过的地方去。生成加油站也是一样的，反正早点生成晚点生成都没有影响，在一条路走到底后再生成不是更好吗？因此上面所有的建边**流量都为** $1$，而不是 $inf$。如果你愿意，用 $inf$ 也没关系，只要把超级源点或超级汇点连出去的边流量设为 $1$ 即可。 ### **【求答案】** 跑一便 $MCMF$ 模板就可以了。最大流为 $1$，最小花费即为答案。 $Q:$ 什么?最大流为 $1$？那和跑最短路有什么区别？直接去掉费用流中 $EK$ 的过程，留下 $SPFA$ 不就是个最短路了吗？ $A:$ 好像没毛病。。。但毕竟这道题考察的是建模能力嘛，只要模型分析了出来，用什么算法实现都无所谓啦！$QAQ

最后再粗略地算一算这道题的空间复杂度：首先是点数，N*N 个坐标，K+1 层，加上超级源、汇点，总点数为：(100*100*11+2=110002)。然后是边数，N*N 个坐标，K+1 层，每层每个坐标要与上下左右四个方向连边，还要与第 0 层连边（表示加油），然后终点的每一层都要与超级汇点相连，最后是超级源点和起点的连边，对于每条边都要同时建一条反向边供我们反悔，总边数为：(N*N*(K+1)*4+K+1)*2=440011*2 。当然，实际上基本达不到这个值。

【Code】

#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=11e4+5,M=6e5+5,inf=2e9;
int x,y,z,w,o=1,n,m,h,t,A,B,C,K,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow; 
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
    for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
    Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w,pre[to]=i;
                cyf[to]=min(cyf[x],a[i].flow);
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
    while(SPFA(st,ed)){
        Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
        while(x!=st){
            Re i=pre[x];
            a[i].flow-=cyf[ed];
            a[i^1].flow+=cyf[ed];
            x=a[i^1].to;
        }
    }
}
inline int P(Re x,Re y,Re k){return (x-1)*n+y+k*n*n;}
int main(){
    in(n),in(K),in(A),in(B),in(C),st=(K+1)*n*n+1,ed=st+1;//一共有(K+1)层 
    add_(st,P(1,1,0),1,0);//超级源点连到满油的起点 
    for(Re k=1;k<=K;++k)add_(P(n,n,k),ed,1,0);
    //把每一层的终点连到超级汇点，所以第0层可以不连 
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=n;++j){
            in(x);
            if(x){//已有加油站 
                for(Re k=1;k<=K;++k)add_(P(i,j,k),P(i,j,0),1,A);
                //所有状态都必须花费A加油加到满，但由于不可能满油到达某一点，所以满油的第0层可以不加（连） 
                //加满油之后状态可以由满油状态到达K-1油的上下左右四个方向 
                if(i<n)add_(P(i,j,0),P(i+1,j,1),1,0);//横坐标+1,费用为0 
                if(j<n)add_(P(i,j,0),P(i,j+1,1),1,0);//纵坐标+1,费用为0 
                if(i>1)add_(P(i,j,0),P(i-1,j,1),1,B);//横坐标-1,费用为B 
                if(j>1)add_(P(i,j,0),P(i,j-1,1),1,B);//纵坐标-1,费用为B 
            }
            else{//无加油站 
                for(Re k=0;k<K;++k){//从有油的状态到达下一层的四个方向 
                    if(i<n)add_(P(i,j,k),P(i+1,j,k+1),1,0);//横坐标+1,费用为0 
                    if(j<n)add_(P(i,j,k),P(i,j+1,k+1),1,0);//纵坐标+1,费用为0 
                    if(i>1)add_(P(i,j,k),P(i-1,j,k+1),1,B);//横坐标-1,费用为B 
                    if(j>1)add_(P(i,j,k),P(i,j-1,k+1),1,B);//纵坐标-1,费用为B 
                }
                add_(P(i,j,K),P(i,j,0),1,A+C);//没有加油站的地方可以自给自足 
            }
        }
    EK(st,ed);//跑一跑模板MCMF 
    printf("%lld",mincost);
}