[网络流24题-8]汽车加油行驶问题-白红宇

[网络流24题-8]汽车加油行驶问题

阅读量：6905 次

发布时间：2019-06-27

本文共 1827 字，大约阅读时间需要 6 分钟。

分层图最短路~~（板子题？总之我不会）~~

看着就很MFMC但是实际上并不是QAQ

看题解第一句话分层就懂了QAQ

大概就是对于一个平面图有多种情况互相转移，那么我们可以对图进行分层

比如说这个题显然可以用油量进行分层

对于几个限制

1.k条边在建图的时候就是油量-1连边就可以了

2.b在建图的同时也可以直接连边

3.加油点的所有出边必须是从油量为k连出去枚举f（0~k-1）连到这个点的k（相当于加满油）边权为c

4.建油站直接枚举f的时候边权是a+c即可

直接上dij或spfa即可（但是spfa他死了）

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 20021225#define ll long long#define mxn 10001using namespace std;struct edge{int to,lt,v;}e[1000001];struct node{    int x,dis;    node(){}    node(int _x,int _dis){x=_x,dis=_dis;}};bool operator <(node a,node b){return a.dis>b.dis;}priority_queue
         
           que;bool vis[1000001];int in[1000001],n,k,cnt,dis[1000001],a,b,c;void add(int x,int y,int v){e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].v=v;in[x]=cnt;}int id(int x,int y,int f){return f*n*n+n*(x-1)+y;}int dij(){ memset(dis,48,sizeof(dis)); dis[id(1,1,k)]=0;//printf("%d\n",id(1,1,k)); que.push(node(id(1,1,k),0)); /**printf("QAQ");*/ while(!que.empty()) { node cur=que.top();que.pop(); if(vis[cur.x]) continue; vis[cur.x]=1;int tmp=dis[cur.x]; for(int i=in[cur.x];i;i=e[i].lt) { int y=e[i].to; if(dis[y]>tmp+e[i].v) { dis[y]=tmp+e[i].v; que.push(node(y,dis[y])); } } } int ans=inf; for(int i=0;i<=k;i++) //{ ans=min(ans,dis[id(n,n,i)]); //printf("%d %d\n",i,dis[id(n,n,i)]); //} return ans;}int mp[101][101];int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};int main(){ 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",&mp[i][j]); for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) { int cc=mp[x][y]?0:c; for(int f=0;f
          
           n||dy>n) continue; if(mp[x][y]) add(id(x,y,k),id(dx,dy,k-1),tmp*b); else for(int f=1;f<=k;f++) add(id(x,y,f),id(dx,dy,f-1),tmp*b); } } printf("%d\n",dij()); return 0;}