汽車加油行駛問(wèn)題

Time Limit:?1 Sec??Memory Limit:?128 MB

Description

給定一個(gè) N*N的方形網(wǎng)格，設(shè)其左上角為起點(diǎn)◎，坐標(biāo)為（ 1，1），X軸向右為正， Y軸向下為正，每一個(gè)方格邊長(zhǎng)為 1，如圖所看到的。一輛汽車從起點(diǎn)◎出發(fā)駛向右下角終點(diǎn)▲，其坐標(biāo)為（ N，N）。在若干個(gè)網(wǎng)格交叉點(diǎn)處，設(shè)置了油庫(kù)，可供汽車在行駛途中加油。汽車在行駛過(guò)程中應(yīng)遵守例如以下規(guī)則：?
(1)汽車僅僅能沿網(wǎng)格邊行駛，裝滿油后能行駛 K條網(wǎng)格邊。出發(fā)時(shí)汽車已裝滿油，在起點(diǎn)與終點(diǎn)處不設(shè)油庫(kù)。?
(2)汽車經(jīng)過(guò)一條網(wǎng)格邊時(shí)，若其 X坐標(biāo)或 Y坐標(biāo)減小，則應(yīng)付費(fèi)用 B，否則免付費(fèi)用。?
(3)汽車在行駛過(guò)程中遇油庫(kù)則應(yīng)加滿油并付加油費(fèi)用 A。?
(4)在須要時(shí)可在網(wǎng)格點(diǎn)處增設(shè)油庫(kù)，并付增設(shè)油庫(kù)費(fèi)用 C（不含加油費(fèi)用 A）。?
(5)(1)～(4)中的各數(shù) N、K、A、B、C均為正整數(shù)，且滿足約束：2 ≤ N ≤ 100，2 ≤ K ≤ 10。設(shè)計(jì)一個(gè)算法，求出汽車從起點(diǎn)出發(fā)到達(dá)終點(diǎn)的一條所付費(fèi)用最少的行駛路線。?

對(duì)于給定的交通網(wǎng)格，計(jì)算汽車從起點(diǎn)出發(fā)到達(dá)終點(diǎn)的一條所付費(fèi)用最少的行駛路線。?

Input

文件的第一行是 N，K，A，B，C的值。第二行起是一個(gè) N*N的 0-1方陣，每行 N個(gè)值，至 N+1行結(jié)束。方陣的第 i行第 j列處的值為 1表示在網(wǎng)格交叉點(diǎn)（ i，j）處設(shè)置了一個(gè)油庫(kù)，為 0時(shí)表示未設(shè)油庫(kù)。各行相鄰兩個(gè)數(shù)以空格分隔。?

Output

輸出最小費(fèi)用

Sample Input

9 3 2 3 60 0 0 0 1 0 0 0 00 0 0 1 0 1 1 0 01 0 1 0 0 0 0 1 00 0 0 0 0 1 0 0 11 0 0 1 0 0 1 0 00 1 0 0 0 0 0 1 00 0 0 0 1 0 0 0 11 0 0 1 0 0 0 1 00 1 0 0 0 0 0 0 0

Sample Output

12

Source

網(wǎng)絡(luò)流24題

? ? 題意依舊不加贅述，題解也不難說(shuō)，就是比裸最短路多幾種轉(zhuǎn)移方式，我不說(shuō)轉(zhuǎn)移方程了，代碼寫得非常美麗。

? ? 1 . 依據(jù)方向的不同要有一個(gè)費(fèi)用B。

? ? 2 . 加油站問(wèn)題，即能夠把油量轉(zhuǎn)移成滿，注意用不用建就可以。

#include <queue> #include <cstdio> #include <cstring> #include <algorithm> #define N 105 #define K 15 #define inf 0x3f3f3f3f using namespace std; const int dx[4]={1,0,-1,0}; const int dy[4]={0,1,0,-1}; struct Lux {int k,x,y;Lux(int a,int b,int c):k(a),x(b),y(c){}Lux(){} };int map[N][N],id[N][N],cnt; int n,p,A,B,C; int dist[K][N][N]; bool in[K][N][N]; Lux s,t;int spfa() {int i,vx,vy,fee,fee2;queue<Lux>q;memset(dist,0x3f,sizeof(dist));dist[s.k][s.x][s.y]=0;in[s.k][s.x][s.y]=1;q.push(s);while(!q.empty()){Lux U=q.front();q.pop();in[U.k][U.x][U.y]=0;if(!U.k)continue;//沒(méi)油了還跑什么for(fee=i=0;i<4;i++){vx=U.x+dx[i];vy=U.y+dy[i];if(i==2)fee=B;/*往回走要多付的費(fèi)用在這里處理了。*/if(!id[vx][vy])continue;if(!map[vx][vy]){fee2=C;/*新開(kāi)油站，準(zhǔn)確的說(shuō)這里的思想是把全圖都開(kāi)成加油站，原加油站強(qiáng)制加油，新加油站不強(qiáng)制，但加油要多付錢*/if(U.k&&dist[U.k-1][vx][vy]>dist[U.k][U.x][U.y]+fee){/*由于加油站強(qiáng)制加油，所以不是加油站才干這么轉(zhuǎn)移。*/dist[U.k-1][vx][vy]=dist[U.k][U.x][U.y]+fee;if(!in[U.k-1][vx][vy])in[U.k-1][vx][vy]=1,q.push(Lux(U.k-1,vx,vy));}}else fee2=0;/*已經(jīng)有原加油站了就不須要再付額外費(fèi)用了*/if(dist[p][vx][vy]>dist[U.k][U.x][U.y]+A+fee+fee2){/*加油的轉(zhuǎn)移*/dist[p][vx][vy]=dist[U.k][U.x][U.y]+A+fee+fee2;if(!in[p][vx][vy])in[p][vx][vy]=1,q.push(Lux(p,vx,vy));}}}int ret=inf;for(i=0;i<=p;i++)ret=min(ret,dist[i][t.x][t.y]);return ret; }int main() { // freopen("test.in","r",stdin);scanf("%d%d%d%d%d",&n,&p,&A,&B,&C);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&map[i][j]),id[i][j]=++cnt;s=Lux(p,1,1),t=Lux(0,n,n);printf("%d\n",spfa());return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/gcczhongduan/p/4297957.html

總結(jié)

以上是生活随笔為你收集整理的【线性规划与网络流24题】汽车加油行驶问题 分层图的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。