PAT-ADVANCED1072——Gas Station

我的PAT-ADVANCED代碼倉：https://github.com/617076674/PAT-ADVANCED

原題連結：https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072

題目描述：

題目翻譯：

1072 加油站

加油站的位置選取，應該使得其與任何住宅之間的最小距離盡可能遠。同時又必須保證所有的居民都在自己的服務範圍内。

現在給你一張城市的地圖和幾個加油站的候選位置，你需要給出最好的建議。如果有超過1種方案，選取離所有住宅平均距離最小的方案。如果方案還不唯一，輸出編号最小的加油站位置。

輸入格式：

每個輸入檔案包含一個測試用例。在每個測試用例中，第一行給出4個正整數：N(<= 1000)，代表房子數量；M(<= 10)，代表加油站的候選位置總數；K(<= 10000)，代表連接配接加油站和房子的道路數目；Ds，代表加油站的最大服務距離。所有房子的編号為1 ~ N。所有加油站的候選位置編号從G1 ~ GM。

接下來的K行，每行以下述形式描述一條道路：

P1 P2 Dist

P1和P2代表道路的兩端點，兩端點均既有可能是房子編号也有可能是加油站的候選位置編号，Dist是道路的長度，是一個整數。

輸出格式：

對每一個測試用例，在第一行輸出最好的加油站選址。第二行輸出該候選位置離房子的最近距離和平均距離。數字必須以一個空格分隔且每個數字精确到小數點後面1位。如果沒有任何解決方案，隻需輸出No Solution。

輸入樣例1：

輸出樣例1：

G1
2.0 3.3

輸入樣例2：

2 1 2 10
1 G1 9
2 G1 20

輸出樣例2：

No Solution

知識點：Dijkstra算法、Bellman-Ford算法、SPFA算法

思路一：Dijkstra算法（鄰接表實作）

首先是輸入的節點标号與加油站編号全部要轉換成數字編号。我假設房子的編号為1 ~ N，加油站的編号為N + 1 ~ N + M。由于輸入的道路兩端有可能是數字也有可能是G開頭的字元串，我們統一用字元串接收，并設定一個函數change()将接收的字元串轉換為數字編号。

我的轉換規則是對G開頭的字元串，取其後面一個字元與字元'0'作差，再傳回N + 內插補點。但是這樣做忽略了G10的情況，是以，當G開頭的字元串長度是3位時，我們需要傳回N + 10。

而我一開始所犯的錯誤是，忽略了N的範圍，N最大可以到達1000。是以這個編号不止有一個字元，我一開始隻考慮了N是個位數的情況。是以我們需要用頭檔案<sstream>中的stringstream類型将數字字元串轉換成數字。

對每個加油站都用Dijkstra算法求其到各個房子的最小距離。

對每個加油站點，首先判斷其到每個房子的最小距離是否小于等于Ds，如果有任何一個值大于Ds，這個加油站點是不可取的。

其次，對可取的加油站點進行篩選。

（1）篩選條件一：與任何住宅之間的最小距離盡可能遠。

（2）篩選條件二：選取離所有住宅平均距離最小的方案。由于住宅總量一定，是以隻需選取離所有住宅總距離最小的方案即可。

（3）篩選條件三：輸出編号最小的加油站位置。這個條件很容易滿足，我們隻需要按編号從小到大周遊即可，對于住宅總距離相等的後續方案不考慮。

注意，在發現離住宅更遠的最小距離後，我們不僅要更新離住宅更遠的最小距離值，還需要更新離所有住宅的總距離。

結果需要四舍五入，我的做法是将離所有住宅的總距離先乘以10再除以N，得到一個浮點數類型。再按同樣的做法，不過這次得到的是一個int類型，将兩者相減，如果差大于等于0.5，就将後面得到的int類型增1，最後輸出結果時還需要再除以10，并保留1位小數。

時間複雜度是O(M * (N + M) ^ 2)。空間複雜度是O(N + M + K)。

C++代碼：

#include<iostream>
#include<vector>
#include<string>
#include<sstream>

using namespace std;

struct node {
	int v;	//節點編号
	int len;	//道路長度
	node(int _v, int _len) : v(_v), len(_len) {}	
};

int N, M, K, Ds, INF = 1000000000;	//房子數量，加油站數量，道路數量，加油站服務範圍，無窮大數 
vector<node> graph[1020]; //無向圖，房子的編号為1 ~ N，加油站的編号為N + 1 ~ N + M
int d[1020];	//記錄最短長度
bool visited[1020];	//标記數組

int totalDistance();
bool validPosition();
int minDistance();
void init();
int change(string s);
void dijkstra(int s);

int main() {
	scanf("%d %d %d %d", &N, &M, &K, &Ds); 
	string P1, P2;
	int Dist;
	for(int i = 0; i < K; i++) {
		cin >> P1 >> P2 >> Dist;
		int id1 = change(P1);
		int id2 = change(P2);
		graph[id1].push_back(node(id2, Dist));
		graph[id2].push_back(node(id1, Dist));
	}
	int minLen = 0;
	int minTotalLen = INF;
	int result = 0;
	for(int i = N + 1; i <= N + M; i++) {
		dijkstra(i);
		if(validPosition()) {
			if(minDistance() > minLen) {
				result = i;
				minLen = minDistance();
				minTotalLen = totalDistance();	//此處也要更新minTotalLen 
			} else if(minDistance() == minLen) {
				if(minTotalLen > totalDistance()) {
					result = i;
					minTotalLen = totalDistance();
				}
			}
		}
	}
	if(result == 0){
		cout << "No Solution" << endl;
		return 0;
	}
	cout << "G" << result - N << endl;
	double average = minTotalLen * 10.0 / N;
	int averageResult = minTotalLen * 10 / N;
	if(average - averageResult >= 0.5){
		averageResult++;
	}
	printf("%.1lf %.1lf\n", minLen * 1.0, averageResult * 1.0 / 10);
	return 0;
}

int totalDistance() {
	int sum = 0;
	for(int i = 1; i <= N; i++) {
		sum += d[i];
	}
	return sum;
}

bool validPosition() {
	for(int i = 1; i <= N; i++) {
		if(d[i] > Ds) {
			return false;
		}
	}
	return true;
}

int minDistance() {
	int min = 1;
	for(int i = 2; i <= N; i++) {
		if(d[i] < d[min]) {
			min = i;
		}
	}
	return d[min];
}

void init() {
	for(int i = 1; i <= N + M; i++) {
		d[i] = INF;
		visited[i] = false;
	}
}

int change(string s) {
	if(s[0] == 'G'){
		if(s.length() == 3){
			return 10 + N;
		}else{
			int num = s[1] - '0';
			return num + N;
		}
	}else{
		stringstream ss;
		ss << s;
		int result;
		ss >> result;
		return result;
	}
}

void dijkstra(int s) {
	init();
	d[s] = 0;
	for(int i = 0; i < N + M; i++) {
		int u = -1, min = INF;
		for(int j = 1; j <= N + M; j++) {
			if(!visited[j] && min > d[j]) {
				min = d[j];
				u = j;
			}
		}
		if(u == -1) {
			return;
		}
		visited[u] = true;
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int len = graph[u][j].len;
			if(!visited[v]) {
				if(d[u] + len < d[v]) {
					d[v] = d[u] + len;
				}
			}
		}
	}
}

C++解題報告：

PAT-ADVANCED1072——Gas Station

思路二：Bellman-Ford算法（鄰接表實作）（測試點4會逾時）

時間複雜度是O(M * K * (N + M))。空間複雜度是O(N + M + K)。

C++代碼：

#include<iostream>
#include<vector>
#include<string>
#include<sstream>

using namespace std;

struct node {
	int v;	//節點編号
	int len;	//道路長度
	node(int _v, int _len) : v(_v), len(_len) {}	//構造函數
};

int N;	//房子數量
int M;	//加油站數量
int K;	//道路數量
int Ds;	//加油站服務範圍
int INF = 1000000000;	//無窮大數
vector<node> graph[1020]; //無向圖，房子的編号為1 ~ N，加油站的編号為N + 1 ~ N + M
int d[1020];	//記錄最短長度

int totalDistance();
bool validPosition();
int minDistance();
void init();
int change(string s);
bool bellmanFord(int s);

int main() {
	cin >> N >> M >> K >> Ds;
	string P1, P2;
	int Dist;
	for(int i = 0; i < K; i++) {
		cin >> P1 >> P2 >> Dist;
		int id1 = change(P1);
		int id2 = change(P2);
		graph[id1].push_back(node(id2, Dist));
		graph[id2].push_back(node(id1, Dist));
	}
	int minLen = 0;
	int minTotalLen = INF;
	int result = 0;
	for(int i = N + 1; i <= N + M; i++) {
		bellmanFord(i);
		if(validPosition()) {
			if(minDistance() > minLen) {
				result = i;
				minLen = minDistance();
				minTotalLen = totalDistance();	//此處也要更新minTotalLen
			} else if(minDistance() == minLen) {
				if(minTotalLen > totalDistance()) {
					result = i;
					minTotalLen = totalDistance();
				}
			}
		}
	}
	if(result == 0) {
		cout << "No Solution" << endl;
		return 0;
	}
	cout << "G" << result - N << endl;
	double average = minTotalLen * 10.0 / N;
	int averageResult = minTotalLen * 10 / N;
	if(average - averageResult >= 0.5) {
		averageResult++;
	}
	printf("%.1lf %.1lf\n", minLen * 1.0, averageResult * 1.0 / 10);
	return 0;
}

int totalDistance() {
	int sum = 0;
	for(int i = 1; i <= N; i++) {
		sum += d[i];
	}
	return sum;
}

bool validPosition() {
	for(int i = 1; i <= N; i++) {
		if(d[i] > Ds) {
			return false;
		}
	}
	return true;
}

int minDistance() {
	int min = 1;
	for(int i = 2; i <= N; i++) {
		if(d[i] < d[min]) {
			min = i;
		}
	}
	return d[min];
}

void init() {
	for(int i = 1; i <= N + M; i++) {
		d[i] = INF;
	}
}

int change(string s) {
	if(s[0] == 'G') {
		if(s.length() == 3) {
			return 10 + N;
		} else {
			int num = s[1] - '0';
			return num + N;
		}
	} else {
		stringstream ss;
		ss << s;
		int result;
		ss >> result;
		return result;
	}
}

bool bellmanFord(int s) {
	init();
	d[s] = 0;
	for(int i = 0; i < N + M - 1; i++) {
		for(int u = 1; u <= N + M; u++) {
			for(int j = 0; j < graph[u].size(); j++) {
				int v = graph[u][j].v;
				int len = graph[u][j].len;
				if(d[u] + len < d[v]) {
					d[v] = d[u] + len;
				}
			}
		}
	}
	for(int u = 1; u <= N + M; u++) {
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int len = graph[u][j].len;
			if(d[u] + len < d[v]) {
				return false;
			}
		}
	}
	return true;
}

C++解題報告：

PAT-ADVANCED1072——Gas Station

思路三：SPFA算法（鄰接表實作）

期望時間複雜度是O(k * M * (N + M))，其中k是一個常數，在很多情況下k不超過2，可見這個算法異常高效，并且經常性地優于堆優化的Dijkstra算法。空間複雜度是O(N + M + K)。

C++代碼：

#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<queue>

using namespace std;

struct node {
	int v;	//節點編号
	int len;	//道路長度
	node(int _v, int _len) : v(_v), len(_len) {}	//構造函數
};

int N;	//房子數量
int M;	//加油站數量
int K;	//道路數量
int Ds;	//加油站服務範圍
int INF = 1000000000;	//無窮大數
vector<node> graph[1020]; //無向圖，房子的編号為1 ~ N，加油站的編号為N + 1 ~ N + M
int d[1020];	//記錄最短長度
bool inq[1020];
int countInq[1020];

int totalDistance();
bool validPosition();
int minDistance();
void init();
int change(string s);
bool spfa(int s);

int main() {
	cin >> N >> M >> K >> Ds;
	string P1, P2;
	int Dist;
	for(int i = 0; i < K; i++) {
		cin >> P1 >> P2 >> Dist;
		int id1 = change(P1);
		int id2 = change(P2);
		graph[id1].push_back(node(id2, Dist));
		graph[id2].push_back(node(id1, Dist));
	}
	int minLen = 0;
	int minTotalLen = INF;
	int result = 0;
	for(int i = N + 1; i <= N + M; i++) {
		spfa(i);
		if(validPosition()) {
			if(minDistance() > minLen) {
				result = i;
				minLen = minDistance();
				minTotalLen = totalDistance();	//此處也要更新minTotalLen
			} else if(minDistance() == minLen) {
				if(minTotalLen > totalDistance()) {
					result = i;
					minTotalLen = totalDistance();
				}
			}
		}
	}
	if(result == 0) {
		cout << "No Solution" << endl;
		return 0;
	}
	cout << "G" << result - N << endl;
	double average = minTotalLen * 10.0 / N;
	int averageResult = minTotalLen * 10 / N;
	if(average - averageResult >= 0.5) {
		averageResult++;
	}
	printf("%.1lf %.1lf\n", minLen * 1.0, averageResult * 1.0 / 10);
	return 0;
}

int totalDistance() {
	int sum = 0;
	for(int i = 1; i <= N; i++) {
		sum += d[i];
	}
	return sum;
}

bool validPosition() {
	for(int i = 1; i <= N; i++) {
		if(d[i] > Ds) {
			return false;
		}
	}
	return true;
}

int minDistance() {
	int min = 1;
	for(int i = 2; i <= N; i++) {
		if(d[i] < d[min]) {
			min = i;
		}
	}
	return d[min];
}

void init() {
	for(int i = 1; i <= N + M; i++) {
		d[i] = INF;
		inq[i] = false;
		countInq[i] = 0; 
	}
}

int change(string s) {
	if(s[0] == 'G') {
		if(s.length() == 3) {
			return 10 + N;
		} else {
			int num = s[1] - '0';
			return num + N;
		}
	} else {
		stringstream ss;
		ss << s;
		int result;
		ss >> result;
		return result;
	}
}

bool spfa(int s) {
	init();
	d[s] = 0;
	queue<int> q;
	q.push(s);
	inq[s] = true;
	countInq[s]++;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		inq[u] = false;
		for(int j = 0; j < graph[u].size(); j++){
			int v = graph[u][j].v;
			int len = graph[u][j].len;
			if(len + d[u] < d[v]){
				d[v] = len + d[u];
				if(!inq[v]){
					q.push(v);
					inq[v] = true;
					countInq[v]++;
					if(countInq[v] > M + N){
						return false;
					}
				}
			}
		}
	}
	return true;
}

C++解題報告：

PAT-ADVANCED1072——Gas Station

PAT-ADVANCED1072——Gas Station

思路一：Dijkstra算法（鄰接表實作）

思路二：Bellman-Ford算法（鄰接表實作）（測試點4會逾時）

思路三：SPFA算法（鄰接表實作）

繼續閱讀

PAT (Advanced Level) Practise 1034 Head of a Gang (30)

PAT (Advanced Level) Practise 1043 Is It a Binary Search Tree (25)

PAT 1044. Shopping in Mars (25) 求區間和，連續序列和

PAT (Advanced Level) Practise 1065 A+B and C (64bit) (20)

PAT (Advanced Level) Practise 1033 To Fill or Not to Fill (25)

PAT (Advanced Level) Practise 1046 Shortest Distance (20)

PAT (Advanced Level) Practise 1100 Mars Numbers (20)

PAT (Advanced Level) Practise 1018 Public Bike Management (30)

PAT (Advanced Level) Practise 1024 Palindromic Number (25)

PAT (Advanced Level) Practise 1012 The Best Rank (25)

資料庫連接配接出現Communications link failure

PAT (Top Level) Practise 1008 Airline Routes (35)

PAT (Top Level) Practise 1007 Red-black Tree (35)

PAT (Advanced Level) Practise 1083 List Grades (25)

PAT (Advanced Level) Practise 1066 Root of AVL Tree (25)

Dijkstra--簡易版（最短路徑）