網絡流24題 之十五 汽車加油行駛問題 分層圖

網絡流24題 之十五 汽車加油行駛問題 分層圖

題目大意：給出一張網格圖，描述了每個點是否是加油站，然後給出以下規則。

1.油量限制，一次加油之後只能行駛k步，向下行駛和向右行駛的時候不增加花費，否則增加B的花費。

2.在沒油的時候，若該點沒有加油站，就建立一個加油站。花費C。

3.加油花費A。

思路：分層圖。f[i][j][k]表示在(i,j)處油箱中還有k的油的時候的最小花費，然後分三種情況更新。

(delta = 往回走的B花費)

1.若當前節點有加油站，就必須加油。到下一個節點是還有k - 1的油量，花費last + A + delta

2.如果當前節點沒有加油站，若當前車裡還有油，就繼續向下更新，花費last + delta

3.如果當前節點沒有加油站，若當前車裡沒有油，就新建一個加油站，花費last + A + C + delta

CODE：

#include 
#include 
#include 
#include 
#include 
#define MAX 110
#define INF 0x3f3f3f3f
using namespace std;
const int dx[5] = {0,1,0,-1,0};
const int dy[5] = {0,0,1,0,-1};

struct Complex{
	int x,y,odd;
	Complex(int _,int __,int ___):x(_),y(__),odd(___) {}
	Complex() {}
};

int cnt,k,add_oil,back_cost,new_cost;
int f[MAX][MAX][20];
bool v[MAX][MAX][20],map[MAX][MAX];

void SPFA();

int main()
{
	cin >> cnt >> k >> add_oil >> back_cost >> new_cost;
	for(int i = 1;i <= cnt; ++i)
		for(int j = 1;j <= cnt; ++j)
			scanf("%d",&map[i][j]);
	SPFA();
	int ans = INF;
	for(int i = 0;i <= k; ++i)
		ans = min(ans,f[cnt][cnt][i]);
	cout << ans << endl;
	return 0;
}

void SPFA()
{
	memset(f,0x3f,sizeof(f));
	f[1][1][k] = 0;
	static queue q;
	while(!q.empty())	q.pop();
	q.push(Complex(1,1,k));
	while(!q.empty()) {
		Complex now = q.front(); q.pop();
		int last = f[now.x][now.y][now.odd];
		v[now.x][now.y][now.odd] = false;
		for(int i = 1;i <= 4; ++i) {
			int detla = (i > 2) * back_cost;
			int fx = now.x + dx[i];
			int fy = now.y + dy[i];
			if(!fx || !fy || fx > cnt || fy > cnt)	continue;
			if(map[now.x][now.y]) {
				if(f[fx][fy][k - 1] > last + add_oil + detla) {
					f[fx][fy][k - 1] = last + add_oil + detla;
					if(!v[fx][fy][k - 1])
						v[fx][fy][k - 1] = true,q.push(Complex(fx,fy,k - 1));
				}	
			}
			else {
				if(!now.odd) {
					if(f[fx][fy][k - 1] > last + add_oil + new_cost + detla) {
						f[fx][fy][k - 1] = last + add_oil + new_cost + detla;
						if(!v[fx][fy][k - 1])
							v[fx][fy][k - 1] = true,q.push(Complex(fx,fy,k - 1));
					}
				}
				else {
					if(f[fx][fy][now.odd - 1] > last + detla) {
						f[fx][fy][now.odd - 1] = last + detla;
						if(!v[fx][fy][now.odd - 1])
							v[fx][fy][now.odd - 1] = true,q.push(Complex(fx,fy,now.odd - 1));
					}
				}
			}
		}
	}
}