【PAT甲级题解记录】1018 Public Bike Management (30 分)

前言

Problem：1018 Public Bike Management (30 分)

Tags：dijkstra最短路径 DFS

Difficulty：剧情模式 想流点汗 想流点血 死而无憾

Address：1018 Public Bike Management (30 分)

问题描述

简单来说就是求单源最短路径，但是每个点都有一定数量的自行车，并且给定一个标准车数，我们要从起点到终点一边走一边调整每个点的车数至标准车数。也就是说我们出发时需要拿一定数量的车，在路上遇到多的可以补充进来，少的就要用出去，最终满足使所有车数都标准。

现在要求最短路径下，出发时拿的车数最小的情况，当拿出最小情况一样，就要求拿回车数最小的情况（车多出来了就要拿回去）。这里很坑，他有三个条件，前两个条件相同情况下还会看第三个，感觉姥姥这题出的太折磨了。（菜是原罪）

也就是说这是一个顺序性的问题，一开始我想着既然可以拿回去，那后面多出来的车可以补给前面，但是写完程序后一交居然发现不行。。。

解题思路

一开始没注意到还有一个拿回数量最小的问题，简单的写了个dijkstra附带最小化点权和，然后就寄了。

但既然dijkstra能把最短路径全都求出来，那我们就可以很快速的从终点利用dfs回溯回去，到起点后再模拟下答案就可以了。

但要是我一开始没看错题的话我就直接dfs了或许更简单毕竟数据不大。

参考代码

/** @Author: Retr0.Wu * @Date: 2022-02-17 16:27:20 * @Last Modified by: Retr0.Wu* @Last Modified time: 2022-02-17 20:02:12*/
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > edge[520]; // 边
vector<int> nums(520, 0);         // 点
vector<bool> visit(520, false);   // 访问集合
vector<int> dis(520, 0x3f3f3f3f); // 实时最短路径
vector<int> pres[520];            // 前点下标
int C_max, N, S_p, M;             // 最大存量1e2 站点数量5e2 问题站点下标 边的数量
vector<int> tracks;
int min_send = 0x3f3f3f3f, min_back = 0x3f3f3f3f;
void dfs(int x, vector<int> v)
{vector<int> v0 = v;v0.push_back(x);if (x == 0) // 到达起点了{int sends = 0, backs = 0;for (int i = v0.size() - 2; i >= 0; i--) // 从原点到终点{int need = C_max / 2 - nums[v0[i]];if (need < 0)  // 有的多{backs += -need; // 拟带回去，先拿上}else  // 不够{if (backs > need) // 手上拿的还够，从手上拿的扣走{backs -= need;}else  {sends += need - backs;  // 手上拿的不够，还需从总部多拿点backs = 0;  // 手上拿着的扣完}}}if (sends < min_send) // 是当下从总部拿最少的方案{tracks = v0;min_send = sends;min_back = backs; // 别忘了back也要一起更新}else if (sends == min_send && backs < min_back) // 从总部拿的数量和之前的方案一样，就要对比拿回去的是不是更少了{tracks = v0;min_back = backs;}return;}for (int i = 0; i < pres[x].size(); i++){dfs(pres[x][i], v0);}
}
void dijkstra()
{dis[0] = 0;pres[0].push_back(-1);for (int iii = 0; iii <= N; iii++){int minn = 0x3f3f3f3f;int mini = 0;for (int i = 0; i <= N; i++){if (!visit[i] && dis[i] < minn){minn = dis[i];mini = i;}}visit[mini] = true;for (int i = 0; i < edge[mini].size(); i++){int nexti = edge[mini][i].first;if (dis[mini] + edge[mini][i].second < dis[nexti]){dis[nexti] = dis[mini] + edge[mini][i].second;pres[nexti].clear();pres[nexti].push_back(mini);}else if (dis[mini] + edge[mini][i].second == dis[nexti]){pres[nexti].push_back(mini);}}}
}
int main()
{cin >> C_max >> N >> S_p >> M; // 最大存量1e2 站点数量5e2 问题站点下标 边的数量for (int i = 1; i <= N; i++){cin >> nums[i];}for (int i = 0; i < M; i++){int v1, v2, w;cin >> v1 >> v2 >> w;edge[v1].push_back(make_pair(v2, w));edge[v2].push_back(make_pair(v1, w));}dijkstra();dfs(S_p, tracks);cout << min_send << " " << tracks[tracks.size() - 1];for (int i = tracks.size() - 2; i >= 0; i--)cout << "->" << tracks[i];cout << " " << min_back << endl;return 0;
}

总结

还是那句话，高分题，题目意思理解透再写，写代码别听太吵的歌，好在这道题难度还好。