【题解】【网络流24题】汽车加油行驶问题 [P4009] [Loj6223]
传送门:汽车加油行驶问题 \([P4009]\) \([Loj6223]\)
【题目描述】
给出一个 \(N \times N\) 的方形网格,设\((1,1)\)为起点,\((N,N)\) 为终点,\(X\) 轴向右为正, \(Y\) 轴向下为正。
某些地方设有油库,可供汽车加油。汽车行驶应遵守如下规则:
\((1).\) 汽车装满油后能行驶 \(K\) 次,每次行驶距离为 \(1\)。出发时汽车为满油状态,在起点与终点处不设油库。
\((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\) 则无。
【输出】
输出最小费用。
【样例】
样例输入:
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
样例输出:
12
【数据范围】
\(100\%\) \(2 \leqslant n \leqslant 100,\) \(2 \leqslant k \leqslant 10\)
【分析】
这明明是一道网络瘤的题中 なのに,但为啥网络瘤的题解基本没几篇啊 \(...\)
解题思路与这位大佬类似:吾王美如画,本篇题解将针对一些细节进行分析。
首先,应该如何建模呢?
【建模】
俗话说得好啊:网络瘤,网络瘤,网络建模最毒瘤。
注意题目描述中加黑字体部分,如果仔细想想的话,会发现出题人特别良心,为我们去除了很多复杂的情况,建模也方便了许多。
先将题目略微修改一下,原题意不变:一份油可供汽车走一个单位长度,油箱最多可装 \(K\) 份油。
\((1).\) 分层:
把每个坐标分为 \(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);
}