1018 Public Bike Management (30point(s))
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:
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.
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
题目意思要好好理解，大致如下：
公共自行车站点管理，每个站点都有个最大容量，当车辆数量为站点最大容量一半时，我们称其状态完美，如果全满或者全空，那就需要调整，其余情况就叫做不完美。
建立一个站点为点，权重为车辆数量，边为距离的图，此时，给出一个需要调整的站点，试找出一条从管理中心到该站点最短的路径，若路径不唯一，就选择其中一路站点顺带调整过去所需要从管理中心发出车辆最少的一条，如果这样的路径还是不唯一，那就选择最后调整完毕需要收回的车辆最少的那一条。
Attention：
- 在站点调整的这一路上，调整的过程是单向的，纵使前一个站点缺车，而后一个站点有富于，也只能要求PBMC发车接济，而不能先去向后一个站点要求其往前调整；但如果情况反过来，即前一个站点多车，后一个站点少车，这样就可以要求从前一个站点直接发车了。这一点逻辑很重要，否则将有一个测试点无法通过。（下面代码中注释掉的部分就是没有弄清楚这样一条具有方向性的传导路径所导致的）
Details:
本来我是想着能不能将判断条件放入Djisktra算法当中去来解决路径挑选问题，后来意识到，路径挑选问题只能是从每条路径整体出发，而不能划分为一个一个子问题放入Djisktra算法中去，于是需要将两步分开走，先通过Djisktra算法获得最短路径，并在这一路上标记好每一个节点的前序节点，然后再通过DFS来处理这些结点（通过记录中的前序关系实现从终点到起点所有可能路径的深度遍历），计算PBMC发出的和收回的车辆数量，进行比较，找出符合条件的最短路径。
Djiskra算法没什么可说的，但是这里面在记录前序节点的时候要注意使用vector数组(vector< int > pre[510])来进行记录，毕竟每一个节点不一定只有一个前序结点啊
if(IsOut[j]==false&&road[picked][j]!=Max){
if(dis[picked]+road[picked][j]<dis[j]){
dis[j]=dis[picked]+road[picked][j];
pre[j].clear();
pre[j].push_back(picked);//refresh the st
}
else if(dis[picked]+road[picked][j]==dis[j])
pre[j].push_back(picked);//refresh the st
}
进行完Djiskra得出最短距离并标定好最短路径上的前序关系之后，就可以对整个存储结构进行DFS了，其中在遍历的过程中，利用一个全局变量temppath来记录当前所选路径的结点，每次遍历在最底一层获得完整的temppath，这时需要利用题中所给的两把标尺来进行比较，选择是否要对path进行更新
if(tempOut<minOut){//第一把标尺，PBMC送出去的车要少
minIn=tempIn;
minOut=tempOut;
path=temppath;
}
else if(tempOut==minOut&&tempIn<minIn){///第二把标尺，PBMC收回来的车要少
minIn=tempIn;
path=temppath;
}
Code：
#include <bits/stdc++.h>
#define Max 0x3f3f3f3f
using namespace std;
int capMax, stNum, roadNum, sP, minIn=Max, minOut=Max;
int st[510]={0}, road[510][510], dis[510];
bool IsOut[510]={false};
vector<int> temppath, path, pre[510];/init pre station condition
void dfs(int v){
temppath.push_back(v);
if(v==0){
int tempIn = 0, tempOut = 0;
for(int i = temppath.size() - 1; i >= 0; i--) {
int id = temppath[i];
if(st[id] > 0) {
tempIn += st[id];
} else {
if(tempIn > abs(st[id])) {
tempIn += st[id];
} else {
tempOut += abs(tempIn+st[id]);
tempIn = 0;
}
}
}
// int cnt=0;//calculate the in and out
// for(int i=temppath.size()-1;i>=0;i--){
// int tempI=temppath[i];
// cnt+=st[tempI];
// }
// int tempIn=0, tempOut=0;
// if(cnt>0){
// tempIn=cnt;
// }
// else if(cnt<0){
// tempOut-=cnt;
// }
if(tempOut<minOut){
minIn=tempIn;
minOut=tempOut;
path=temppath;
}
else if(tempOut==minOut&&tempIn<minIn){
minIn=tempIn;
path=temppath;
}
temppath.pop_back();
return ;
}
for(int i=0;i<pre[v].size();i++)
dfs(pre[v][i]);
temppath.pop_back();
}
int main(){
memset(dis,Max,sizeof(dis));
memset(road,Max,sizeof(road));
cin>>capMax>>stNum>>sP>>roadNum;
for(int i=1;i<=stNum;i++){//init station current num
cin>>st[i];
st[i]=st[i]-(capMax/2);
}
for(int i=0;i<roadNum;i++){//init road
int j_1,j_2,t;
cin>>j_1>>j_2>>t;
road[j_1][j_2]=road[j_2][j_1]=t;
}
dis[0]=0;
for(int i=0;i<stNum+1;i++){//implement djistra
int picked=-1,mindis=Max;
for(int j=0;j<=stNum;j++){pick out the one with shortest path
if(dis[j]<mindis && IsOut[j]==false){
picked=j;
mindis=dis[j];
}
}
if(picked==-1) break;
then refreash the dis left
IsOut[picked]=true;
for(int j=0;j<=stNum;j++){
if(IsOut[j]==false&&road[picked][j]!=Max){
if(dis[picked]+road[picked][j]<dis[j]){
dis[j]=dis[picked]+road[picked][j];
pre[j].clear();
pre[j].push_back(picked);//refresh the st
}
else if(dis[picked]+road[picked][j]==dis[j])
pre[j].push_back(picked);//refresh the st
}
}
}
dfs(sP);
cout<<minOut<<" 0";
for(int i=path.size()-2;i>=0;i--)
cout<<"->"<<path[i];
cout<<" "<<minIn;
return 0;
}
Summary and harvest
(for my current level)
复习：
- Djisktra算法
（4）、Dijkstra算法求解实际问题
之前讲的是最基本的Dijkstra算法，那么平时考试笔试等遇到的题目肯定不会这么“裸”，更多时候会出现这样一种情况，即从起点到终点的最短距离最小的路径不止一条。
那么碰到这种两条以上可以达到最短距离的路径，题目就会给出一个第二标尺（第一标尺是距离），要求在所有最短路径中选择第二标尺最优的一条路径，而第二标尺常见的是以下三种出题方法或者其组合：
给每条边在增加一个边权（比如说花费），然后要求在最短路径有多条时要求路径上的花费之和最小（当然如果边权是其它含义，也可以是最大）
给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径有多条时要求路径上的点权之和最大（当然如果是其它含义，也可以是最小）
直接问有多少条最短路径
解决思路：都只需要增加一个数组来存放新增的边权或点权或最短路径条数，然后在Dijkstra算法中修改优化d[v]的那个步骤即可，其它部分不需要改动。
- C 库函数 - memset()
描述
C 库函数 void *memset(void *str, int c, size_t n) 复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。
声明
下面是 memset() 函数的声明。
void *memset(void *str, int c, size_t n)
参数
str – 指向要填充的内存块。
c – 要被设置的值。该值以 int 形式传递，但是函数在填充内存块时是使用该值的无符号字符形式。
n – 要被设置为该值的字节数。
在进行批量初始化的时候还是尽量选用memset这个函数，因为我发现有的时候用数组={ value };的方法进行初始化还是会失效，用memset这个方法就更稳妥一点
![Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)