(PAT 1018) Public Bike Management (Dijstra+DFS)

朱雀 2022-03-20 15:23 163阅读 0赞

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in **perfect** condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

![213][]

The above figure illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

1.  PBMC -> S1 -> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions.
2.  PBMC -> S2 -> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (≤100), always an even number, is the maximum capacity of each station; N (≤500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,⋯,N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

### Output Specification: ###

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0−>S1−>⋯−>Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge's data guarantee that such a path is unique.

### Sample Input: ###

10 3 3 5
    6 7 0
    0 1 1
    0 2 1
    0 3 3
    1 3 1
    2 3 1

### Sample Output: ###

3 0->2->3 0

解题思路:

本题难点在于最后路径的选择上

题目的意思是,从起点出发到达终点,把途经的每个结点的权值调成Cmax/2,问需要最少额外自行车的路径是哪一条,需要额外多少辆自行车?需要带回多少辆

我们首先把每个结点的权值减去Cmax/2,这样我们就得到了每个结点多多少辆自行车或是少多少辆自行车

我们首先通过Dijsktra算法得到多条最短路,然后通过DFS筛选,遍历时如果结点权值为正数,那么将这些自行车带上,如果为负数,那么将这些带上的自行车用于补充,如果带上的自行车不够补充,那么我们就需要额外的自行车补足

最后求需要额外自行车数量最少的那条路,如果数量相等,则选择需要待会自行车最少的那条

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <math.h>
    using namespace std;
    const int MAXV = 510;
    const int INF = 0x3fffffff;
    int Cmax, N, Sp, M;
    int startPoint;
    int BMap[MAXV][MAXV];
    int Bd[MAXV];  //切记一定要初始化
    bool BVisited[MAXV] = { false };
    int BWeight[MAXV];
    //路径
    int MinNeed = INF, MinBack = INF;
    
    vector<int> Bpres[MAXV];
    vector<int> bestPath, tempPath;
    
    void BDijkstra(int s) {
    	fill(Bd, Bd + MAXV, INF);
    	Bd[s] = 0;  //起点初始化
    	for (int i = 0; i <= N; ++i) {
    		int u = 1, MMin = INF;
    		for (int j = 0; j <= N; ++j) {
    			if (!BVisited[j] && Bd[j] < MMin) {
    				MMin = Bd[j];
    				u = j;
    			}
    		}
    		if (u == -1) return;
    		//开放边
    		BVisited[u] = true;
    		for (int v = 0; v <= N; ++v) {
    			if (!BVisited[v] && BMap[u][v] != INF) {
    				if (BMap[u][v] + Bd[u] < Bd[v]) {
    					Bd[v] = BMap[u][v] + Bd[u];
    					Bpres[v].clear();
    					Bpres[v].push_back(u);
    				}
    				else if (BMap[u][v] + Bd[u] == Bd[v]) {
    					Bpres[v].push_back(u);
    				}
    			}
    		}
    	}
    }
    
    void BDfs(int v) {
    	if (v == startPoint) {
    		tempPath.push_back(v);
    		int remain = 0, need = 0;
    		for (int i = tempPath.size() - 1; i >= 0; --i) {
    			if (BWeight[tempPath[i]] >= 0) {
    				remain += BWeight[tempPath[i]];
    			}
    			else {
    				if (remain >= abs(BWeight[tempPath[i]])) {
    					remain -= abs(BWeight[tempPath[i]]);
    				}
    				else {
    					need += abs(BWeight[tempPath[i]]) - remain;
    					remain = 0;
    				}
    			}
    		}
    
    		if (need < MinNeed) {
    			MinNeed = need;
    			MinBack = remain;
    			bestPath = tempPath;
    		}
    		else if (need == MinNeed && remain < MinBack) {
    			MinBack = remain;
    			bestPath = tempPath;
    		}
    		tempPath.pop_back();
    		return;
    	}
    	//回溯
    	tempPath.push_back(v);
    	for (int i = 0; i < Bpres[v].size(); ++i) {
    		BDfs(Bpres[v][i]);
    	}
    	tempPath.pop_back();
    }
    
    int main() {
    	fill(BMap[0], BMap[0] + MAXV * MAXV, INF);
    	startPoint = 0;
    	scanf("%d %d %d %d", &Cmax, &N, &Sp, &M);
    	BWeight[0] = 0;  //0是起点
    	for (int i = 1; i <= N; ++i) {
    		scanf("%d", &BWeight[i]);
    		BWeight[i] -= (Cmax / 2);
    	}
    	int node1, node2, nLen;
    	for (int i = 0; i < M; ++i) {
    		scanf("%d %d %d", &node1, &node2, &nLen);
    		BMap[node1][node2] = nLen;
    		BMap[node2][node1] = nLen;
    	}
    	BDijkstra(startPoint);
    	BDfs(Sp);
    
    	printf("%d ", MinNeed);
    	for (int i = bestPath.size() - 1; i >= 0 ; --i) {
    		printf("%d", bestPath[i]);
    		if (i > 0) printf("->");
    	}
    	printf(" %d", MinBack);
    	system("PAUSE");
    	return 0;
    }

[213]: /images/20220320/936a629423df4c27b62b0cca4be2bfa0.png