【网络流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

第一行是N，K，A，B，C的值。
第二行起是一个N * N 的0-1 方阵，每行N 个值，至N+1 行结束。方阵的第i 行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻两个数以空格分隔。

Output

最小费用

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

思路：最短路。将点(i,j)分为(i,j,0)(i,j,1)(i,j,2)...(i,j,K)分别连边。代表此时在点(i,j)还能走K条网格边。

设要从(a,b)向(c,d)连边（两点有公共边），则：

若(c,d)是油库,则(a,b,s)向(c,d,K)连权值为a+B的边(s=0..K)

否则(a,b,s)向(c,d,s-1)连权值为B的边(s=1..K)

注意没有的情况，对每个(i,j),(i,j,0)向(i,j,K)连权值为a+C的边

解释：B:若边是反方向，B==b，否则B==0

C：若(i,j)是油库，C==0,否则C==c

ps.裸的最短路我以为是网络流。。。

 1 // It is made by XZZ
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 #define rep(a,b,c) for(rg int a=b;a<=c;a++)
 7 #define drep(a,b,c) for(rg int a=b;a>=c;a--)
 8 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
 9 #define il inline
10 #define rg register
11 #define vd void
12 #define t (dis[i])
13 typedef long long ll;
14 il int gi(){
15     rg int x=0;rg char ch=getchar();
16     while(ch<'0'||ch>'9')ch=getchar();
17     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
18     return x;
19 }
20 int num[111][111][12];
21 char yes[111][111];
22 const int maxn=111*111*12,maxm=maxn<<2;
23 const int X[]={23333,0,0,1,-1},Y[]={23333,1,-1,0,0},C[]={23333,0,1,0,1};
24 int fir[maxn],nxt[maxm],dis[maxm],w[maxm],id=1;
25 il vd add(int a,int b,int c){
26     nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;
27 }
28 il int spfa(int n,int K){
29     int que[maxn],hd=0,tl=1,Dis[maxn];bool inque[maxn]={0};
30     que[hd]=num[1][1][K],inque[num[1][1][K]]=1;
31     memset(Dis,127/3,sizeof Dis),Dis[num[1][1][K]]=0;
32     while(hd-tl){
33         int now=que[hd];hd=(hd+1)%maxn,inque[now]=0;
34         erep(i,now)
35             if(Dis[now]+w[i]<Dis[t])
36                 Dis[t]=Dis[now]+w[i],(inque[t]?666666:que[tl]=t,inque[t]=1,tl=(tl+1)%maxn);
37     }
38     int ret=2123333333;
39     rep(i,0,K)ret=min(ret,Dis[num[n][n][i]]);
40     return ret;
41 }
42 int main(){
43     int n=gi(),K=gi(),a=gi(),b=gi(),c=gi(),Id=0;
44     rep(i,1,n)rep(j,1,n)while(yes[i][j]!='0'&&yes[i][j]!='1')yes[i][j]=getchar();
45     rep(i,1,n)rep(j,1,n)rep(k,0,K)num[i][j][k]=++Id;
46     rep(i,1,n)rep(j,1,n)
47         if(yes[i][j]=='0')add(num[i][j][0],num[i][j][K],a+c);
48         else add(num[i][j][0],num[i][j][K],a);
49     rep(i,1,n)rep(j,1,n)rep(k,1,K)
50         rep(s,1,4)if(i+X[s]&&i+X[s]<=n&&j+Y[s]&&j+Y[s]<=n)
51             if(yes[i+X[s]][j+Y[s]]=='0')
52                 add(num[i][j][k],num[i+X[s]][j+Y[s]][k-1],C[s]*b);
53             else
54                 add(num[i][j][k],num[i+X[s]][j+Y[s]][K],a+C[s]*b);
55     printf("%d
",spfa(n,K));
56     return 0;
57 }

View Code