[网络流24题]汽车加油行驶问题（分层图）

题意

链接

思路

假的网络流

由于无法直接储存油量这个状态，加上k很小，可以把原图分层，分为k+1层图，分别表示当前油量为0~k

连边

对于满油的第k层，连给四个方向，如果向回走了权值为B，否则为0，表示走一步

对于非满油层，如果当前点是加油站，那么它只有一条指向第k层对应点的边，权值为A，表示加一次油

对于非满油层，如果当前节点不是加油站，那么它可以连给下一层对应的四个方向，同1；它也有一条连向第k层对应点的边，权值为A+C，表示建立加油站并且加一次油（由于网格图上的每一个点最多走一次，所以这样连边的正确性可以保证）

最后将终点所对应的k+1个点连给汇点t，边权为0

从第k层的s点出发跑最短路，dis[t]，即为答案

Code：

#include<bits/stdc++.h> #define N 200005 #define M 2000005 using namespace std; int n,k,A,B,C,s,t; int a[105][105]; int dis[N]; bool vis[N]; struct Node { int u,dis; bool operator < (const Node a)const { return a.dis<dis; } }; struct Edge { int next,to,dis; }edge[M];int head[N],cnt; void add_edge(int from,int to,int dis) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].dis=dis; head[from]=cnt; } void dijkstra(int s) { memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); priority_queue<Node> q; q.push((Node){s,0}); dis[s]=0; while(!q.empty()) { int u=q.top().u;q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis) { dis[v]=dis[u]+edge[i].dis; if(!vis[v]) q.push((Node){v,dis[v]}); } } } } int main() { scanf("%d%d%d%d%d",&n,&k,&A,&B,&C); s=1;t=N-5; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]); //代码中i=0为满油层 for(int i=0;i<=k;++i) for(int j=1;j<=n;++j) for(int p=1;p<=n;++p) { int id=(j-1)*n+p,step=n*n; if(!a[j][p]||!i)//不是加油站，可以向四周连边；或者满油位置 { if(i!=k)//还有油 { if(p!=n) add_edge(step*i+id,step*(i+1)+id+1,0);//向右 if(p!=1) add_edge(step*i+id,step*(i+1)+id-1,B);//向左 if(j!=n) add_edge(step*i+id,step*(i+1)+id+n,0);//向下 if(j!=1) add_edge(step*i+id,step*(i+1)+id-n,B);//向上 } } if(a[j][p]&&i) add_edge(step*i+id,id,A);//加油站 if(!a[j][p]&&i) add_edge(step*i+id,id,A+C);//新建加油站 } for(int i=0;i<=k;++i) add_edge(n*n*(i+1),t,0);//连终点 dijkstra(s); cout<<dis[t]<<endl; return 0; }

转载于:https://www.cnblogs.com/Chtholly/p/11325010.html