「网络流24题」汽车加油行驶问题
题目描述 Description
给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X 轴向右为正，Y
轴向下为正，每个方格边长为1，如图所示。一辆汽车从起点◎出发驶向右下角终点▲，其
坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在
行驶过程中应遵守如下规则：(1)汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起
点与终点处不设油库。
(2)汽车经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。
(3)汽车在行驶过程中遇油库则应加满油并付加油费用A。
(4)在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。
(5)(1)～(4)中的各数N、K、A、B、C均为正整数，且满足约束：2 £ N £ 100，2 £ K £ 10。
设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。
输入描述 Input Description
第一行是N，K，A，B，C的值。第二行起是一
个N*N 的0-1 方阵，每行N 个值，至N+1 行结束。方阵的第i 行第j 列处的值为1 表示在
网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻两个数以空格分隔。
输出描述 Output Description
程序运行结束时，将最小费用输出
样例输入 Sample Input
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
样例输出 Sample Output
12
题解
按照油箱中剩余油量建立K层图，汽车在地图上点i，剩余油量为l时，对应点为<i,l>。
1、如果油箱不满(l<K)，点i为油库点，从<i,l>到<i.top>建立一条权值为A的有向边。
2、如果油箱不满(l<K)，点i不为油库点，从<i,l>到<i.top>建立一条权值为A+C的有向边。
3、如果油箱不为空，i不为油库点，每层l从<i.l>到<j.l-1>建立一条权值为0的有向边，其中j为i的右边或下边相邻的一个顶点；从<i.l>到<j.l-1>建立一条权值为B的有向边，其中j为i的左边或上边相邻的一个顶点。
4、如果油箱不为空，i为油库点，从<i.K>到<j.K-1>建立一条权值为0的有向边，其中j为i的右∑边或下边相邻的一个顶点；从<i.K>到<j.K-1>建立一条权值为B的有向边，其中j为i的左边或上边相邻的一个顶点。
求从<(1,1),K>的单源最短路径，到达目标的最小费用就是Min{dist[<(N,N),k>] | 0 <= k <= K }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int cnt,n,k,a,b,c,mark[101][101],mp[101][101],dis[120001],q[120001],head[120001]; bool inq[120001]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; struct data{int to,next,v;}e[1000001]; void insert(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void spfa() { int t=0,w=1,i,now; memset(dis,127/3,sizeof(dis)); q[0]=0;dis[0]=0;inq[0]=1; while(t!=w) { now=q[t];t++;if(t==10001)t=0;i=head[now]; while(i) { if(dis[now]+e[i].v<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]) { inq[e[i].to]=1; q[w++]=e[i].to; if(w==10001)w=0; } } i=e[i].next; } inq[now]=0; } } 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]); mark[i][j]=((i-1)*n+j-1)*11+1; } insert(0,1+k,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int l=0;l<k;l++) if(mp[i][j])insert(mark[i][j]+l,mark[i][j]+k,a); else insert(mark[i][j]+l,mark[i][j]+k,a+c); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int d=0;d<4;d++) { int nowx=i+xx[d],nowy=j+yy[d]; if(nowx>n||nowy>n||nowx<1||nowy<1)continue; if(mp[i][j]) if(nowx<i||nowy<j)insert(mark[i][j]+k,mark[nowx][nowy]+(k-1),b); else insert(mark[i][j]+k,mark[nowx][nowy]+(k-1),0); else { for(int l=1;l<=k;l++) if(nowx<i||nowy<j)insert(mark[i][j]+l,mark[nowx][nowy]+(l-1),b); else insert(mark[i][j]+l,mark[nowx][nowy]+(l-1),0); } } spfa(); int ans=0x7fffffff; for(int i=0;i<=k;i++)ans=min(dis[mark[n][n]+i],ans); printf("%d\n",ans); return 0; } |
OI 课件=>
