PAT (Advanced Level) Practice - 1018 Public Bike Management（30 分）

PAT (Advanced Level) Practice - 1018 Public Bike Management（30 分）

​

题目大意：每个自行车车站的最大容量为一个偶数cmax，如果一个车站里面自行车的数量恰好为cmax / 2，那么称处于完美状态。如果一个车站容量是满的或者空的，控制中心（处于结点0处）就会携带或者从路上收集一定数量的自行车前往该车站，一路上会让所有的车站沿途都达到完美。现在给出cmax，车站的数量n，问题车站sp，m条边，还有距离，求最短路径。如果最短路径有多个，求能带的最少的自行车数目的那条。如果还是有很多条不同的路，那么就找一个从车站带回的自行车数目最少的。带回的时候是不调整的。

解题思路：Dijkstra + DFS。如果只有Dijkstra是不可以的，因为minNeed和minBack在路径上的传递不满足最优子结构，不是简单的相加的过程，只有在所有路径都确定了之后才能区选择最小的need和最小的back。

Dijkstra求最短路径，dfs求minNeed和minBack和最终path，dfs的时候模拟一遍需要调整的过程，求出最后得到的need和back，与minNeed和minBack比较然后根据情况更新path，最后输出 minNeed path 和 minBack，记得path是从最后一个结点一直到第一个结点的，所以要倒着输出。

AC 代码

#include#include#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=520;int n,mined,mibak;int wrr[maxn], vis[maxn], dis[maxn];int g[maxn][maxn];vector pre[maxn], tpath, path;void init(){ mined=mibak=INF; mem(dis,INF); mem(g,INF); mem(vis,0); mem(wrr,0);}int dijkstra(int s){ dis[s]=0; while(1) { int mi=INF; s=-1; for(int i=0;i<=n;i++) if(!vis[i] && dis[i]=0;i--) { int u=tpath[i], w=wrr[u]; if(w>0) bak+=w; else { if(bak>-w) bak+=w; else { ned+=-w-bak; bak=0; } } } if(ned=0;i--) printf("%d%s",path[i],i==0?"":"->"); printf(" %d\n",mibak); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。