1018 Public Bike Management
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.
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
题意
给定车站的信息，公共自行车管理中心（PBMC）不断监测所有站点的实时容量。
如果一个车站自行车存量刚满一半，则称其处于理想状态。
如果一个车站已满或空了，PBMC 会收集或派送自行车以将该车站的状况调整到最佳状态。
而且，途中的所有车站也会调整至最佳。
现在给定需要调整的站点，PBMC 将始终选择到达该站点的最短路径，前去该站点进行车辆调整。
如果最短路径多于一条，则将选择需要从 PBMC 发送的自行车数量最少的那条路径。如果还出现相同的路径，则选择那条调整完后带回 PBMC 车辆数量最小的路径。
上图给出了一个示例，车站以及 PBMC 由点表示，道路由边表示。
边上的数字是从一个站点到达另一个站点所花费的时间。
点内的数字是车站目前的自行车存量。
假设每个站点最多存 10 辆车。
我们现在要给车站 S3 送自行车，共有两条最短路径可选：
1.PBMC→S1→S3 ，这种路线需要从 PBMC 发送 4 辆自行车，因为我们可以从 S1 收集 1 辆车，并需要给 S3 派送 5 辆车，这样两个站点就都调整到最佳状态了。
2.PBMC→S2→S3 ，这种路线与上一条路线距离相同，但是只需要从 PBMC 发送 3 辆自行车，因此这条路径应该被选择。
思路
这道题不能只用迪杰斯特拉就去计算出最佳方案，因为我们并不清楚从总部到需要调整的车站过程中需要填补多少车辆或带走多少车辆，没有一个比较的指标。
故需要分开进行计算，首先先去计算一遍从总部到终点的最短路径，这里我们用迪杰斯特拉算法进行计算，并且是从终点往总部去计算，这样方便我们后续进行比较（在下面会详细的说明）。
然后再从总部往终点进行递归运算，找到带出车辆数以及带回车辆数的最佳方案。
这里就需要重点注意，我们用了一个变量 s 来表示我们需要从总部带出的车辆数，在到终点的过程中会计算需要填补车辆的数量或带走车辆的数量，如果一个站点需要带走车辆，则 s 会加上带走的车辆数；相反如果一个站点需要填补车辆，则 s 会减去需要填补的车辆数。如果 s 最终为正数，则说明在到终点时，我们在路上收集到的车辆足够填补终点缺的车辆，故我们不需要从总部带出车辆，即带出车辆数为 0 ，但带回车辆数为 s ；相反如果 s 最终为负数，则说明我们到终点时，路上收集到的车辆不足以填补终点缺的车辆，甚至路上还需要填补额外的车辆，故这个 s 的绝对值就是我们需要从总部带出去的车辆数，且带回的车辆数就为 0 。
另外，我们还需要知道在 dfs 的过程中如何找到之前计算出的最短路径，因为在迪杰斯特拉算法中是从终点往总部去计算，所以从总部到终点的最短距离是存在了 dist[0] 即总部的位置。而我们 dfs 是从总部出发往终点去递归，所以可以利用公式 dist[u] == dist[i] + g[u][i] 来找到最短的路径。这个公式的意思是，从终点到当前站点 u 的最短距离 dist[u] 如果等于从终点到站点 i 的最短距离 dist[i] 加上从站点 u 到站点 i 的距离，则说明 i 就是最短路径中的一点，直接往 i 继续遍历即可，这也解释了为什么要从终点往回计算最短路径，我们可以看看下面这张图：
计算完之后，最终要先输出带出的车辆数，再输出最短路径，最后输出带回的车辆数，注意输出的末尾不能有空格。
代码
#include<bits/stdc++.h> using namespace std; const int N = 510, INF = 0x3f3f3f3f; int C, n, S, m; int c[N]; int g[N][N]; int dist[N]; bool st[N]; vector<int> path, ans; int send = INF, bring = INF; void dijkstra() { //初始化 memset(dist, 0x3f, sizeof dist); dist[S] = 0; //从终点往回计算 for (int i = 0; i < n; i++) { int t = -1; for (int j = 0; j <= n; j++) //找到一条当前的最短边 if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for (int j = 0; j <= n; j++) if (dist[j] > dist[t] + g[t][j]) dist[j] = dist[t] + g[t][j]; } } void dfs(int u, int s, int mins) { if (u) //起点不算进去 { s -= (C + 1) / 2 - c[u]; //计算当前站点需要带走或填补的车辆数 mins = min(mins, s); //记录需要最大带出的车辆数 } if (u == S) //如果到了终点，判断是否是最佳路径 { int sd = abs(min(mins, 0)); //需要带出的车辆数 int bg = sd + s; //需要带回的车辆数 //更新信息 if (sd < send) send = sd, bring = bg, ans = path; else if (sd == send && bg < bring) bring = bg, ans = path; return; } //找到最短路径上的结点进行遍历 for (int i = 1; i <= n; i++) if (dist[u] == dist[i] + g[u][i]) { path.push_back(i); dfs(i, s, mins); path.pop_back(); } } int main() { cin >> C >> n >> S >> m; //输入每个站点的自行车数量 for (int i = 1; i <= n; i++) cin >> c[i]; //输入每一条道路 memset(g, 0x3f, sizeof g); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; g[a][b] = g[b][a] = min(g[a][b], c); } //从终点往回计算最短路 dijkstra(); //计算带出车辆和带回车辆的最佳方案 path.push_back(0); dfs(0, 0, 0); //输出最终结果 cout << send << " 0"; for (int i = 1; i < ans.size(); i++) cout << "->" << ans[i]; cout << " " << bring << endl; return 0; }
