关于算法-数据结构:PAT甲级1018-Public-Bike-Management

题目粗心:

城市外面有一些公共自行车站, 每一个车站最大包容 Cmax 辆车, 如果该车站的车辆当初有 Cmax/ 2 辆车, 那么阐明它处于 perfect 状态, 当初有一个站点 Sp 汇报有问题，须要控制中心 (PBMC) 就会找到一条间隔它最短的门路, 携带或者在路上回收多余的车辆带到 Sp, 使得它是 perfect 的状态, 并且将多余车辆带回 PBMC, 当初要求找一条从 PBMC 到 Sp 的最短门路, 如果该门路有多条，抉择从 PBMC 携带车辆起码的，如果还有多条，抉择从 Sp 回来的时候带回 PBMC 车辆起码的, 题目保障有且仅有一条数据。

算法思路：

依据题目形容是一个典型的单源最短门路问题, 应用 Dijstra 算法求解最短门路, 因为波及到要输入具体的门路, 所以采纳 Dijstra+DFS 的办法, 先应用 Dijstra 算法求得 PBMC 到 Sp 的间隔最短的所有门路, 而后再用 DFS 遍历所有门路抉择合乎第二标尺, 也就是 PBMC 携带车辆起码的或者带回 PBMC 车辆起码的门路.

数据的存储：

应用 G 存储图,visited 为拜访标记数组,bikes_number 数组为每个结点的点权,pre 数组保留每个结点的所有前驱结点,shortest 为 DFS 遍历中保留单条门路，result 用来保留最优门路，dis 数组保留终点到其余节点的最短距离,min_need_sent_bike 示意起码须要终点派送的车辆数目,min_need_back_bike 示意须要起码须要从起点送回的车辆数目

Dijkstra 算法求解

咱们循环 N 次，每一次循环，首先从所有未拜访的点中找到间隔终点最小的点 nearest, 而后再优化借助 nearest 到其余未拜访的点的最短距离，如果借助 nearest 达到以后点 j 更短，那么就更新达到 j 的最短距离，最小消耗和达到 j 的前驱节点。如果最短距离一样然而通过 nearest 达到 j 的消耗更小，那么就更新达到 j 的最小消耗和 j 的前驱节点。

DFS 算法过程：

在遍历所有最短门路的过程中须要重点强调的是调整结点状态的形式，肯定得是从终点开始顺次调整每一个节点的状态，其它的办法基本不可行，间隔终点较近的节点的车辆数目较少，然而间隔终点较远的车辆数目较多且恰好能够满足，这种状况下还是得从终点派送车辆调整车辆少的节点，并且将多余的车辆带回，也就是说，不能应用 $n*(Cmax/2)$ 的形式获得最佳车辆总数, 而后用现有门路的车辆总数比拟相减，因为就算最初一个结点有十分多的车辆, 也没有方法奉献给在门路后面的结点, 题目的原话为

all the stations on the way will be adjusted as well.

也就是单向调整的。咱们每次取得一条最短门路，就从终点的下一个节点开始遍历，如果以后车辆过多就须要带走，应用 need_back_bike 记录带回的车辆数目，如果以后站点车辆过少，就须要先应用在路上收集到的车辆进行填补，如果不够再从终点进行派送，need_sent_bike 记录派送的车辆数目，如果以后门路须要派送的车辆数目更少或者派送数目雷同，然而带回车辆数目更少，就更新 min_need_sent_bike，min_need_back_bike 和 result。

留神点：

• 1、调整方向为单向调整，不能应用前面站点多余的车辆填补后面的站点。
• 2、从路上收集的车辆数目不够用的时候，得先填补以后站点车辆的空缺，再将 need_back_bike 置为 0.

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int Cmax,N,Sp,M;// 最大容量，站点个数，问题站点编号，路线数量 
int bikes_number[505];// 点权，每一个站点的车辆数目
int G[505][505];// 边权，两站点之间消耗工夫
bool visited[505];// 拜访标记数组
int dis[505];// 每一个站点到终点的间隔 
vector<int> pre[505];// 保留每一个站点的前驱结点
vector<int> shortest;// 最短门路
vector<int> result;// 最优门路
int min_need_sent_bike = 0x3fffffff;// 起码须要终点派送的车辆数目
int min_need_back_bike = 0x3fffffff;// 起码须要从起点送回的车辆数目 

// 应用深度优先搜寻找到须要派送车辆起码的最短门路 
void DFS(int start){
    // 先拜访以后节点 
    shortest.push_back(start);
    if(pre[start].empty()){
        // 以后节点是终点，没有前驱, 计算该门路上须要派送的车辆
        int need_sent_bike = 0;// 须要派送的车辆数目 
        int need_back_bike = 0;// 须要送回的车辆数目 
        int perfect_bike = Cmax/2;// 完满状态车辆数目 
        for(int i=shortest.size()-2;i>=0;--i){// 循环得排除终点 
            if(bikes_number[shortest[i]]>perfect_bike){
                // 车辆过多须要带走
                need_back_bike +=  (bikes_number[shortest[i]]-perfect_bike);
            }else if(bikes_number[shortest[i]]<perfect_bike){
                // 以后站点, 车辆过少
                int need =  perfect_bike-bikes_number[shortest[i]];// 以后站点须要的车辆数目 
                if(need_back_bike>=need){
                    // 从路上收集的车辆数目够用
                    need_back_bike -= need;// 这里得是累减 
                }else {
                    // 不够用
                    need_sent_bike += need-need_back_bike;// 须要派送残余须要车辆, 这里得是累加 
                    need_back_bike = 0;// 这句话得在前面 
                }
            }
        }
        if(need_sent_bike<min_need_sent_bike){
            // 以后门路须要派送的车辆数目更少 
            min_need_sent_bike = need_sent_bike;
            min_need_back_bike = need_back_bike;
            result = shortest;
        }else if(need_sent_bike==min_need_sent_bike&&min_need_back_bike>need_back_bike){
            // 派送车辆一样，须要送回的车辆更少 
            min_need_back_bike = need_back_bike;
            result = shortest;
        }
        shortest.pop_back();
        return;
    }
    for(int i=0;i<pre[start].size();++i){DFS(pre[start][i]);
    }
    // 以后结点及其前驱都拜访结束, 回溯 
    shortest.pop_back();}

void Dijkstra(){
    // 初始化 
    fill(dis,dis+505,0x3fffffff);
    dis[0] = 0;
    // 循环 N + 1 次
    for(int i=0;i<=N;++i){
        // 首先从所有未拜访的点中找到间隔终点最小的点 
        int nearest,minDis=0x3fffffff;
        for(int j=0;j<=N;++j){if(!visited[j]&&minDis>dis[j]){
                nearest = j;
                minDis = dis[j];
            }
        }
        if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 
        // 优化借助 nearest 到其余未拜访的点的间隔
        visited[nearest] = true;
        for(int j=0;j<=N;++j){if(!visited[j]&&G[nearest][j]!=0){if(dis[j]>dis[nearest]+G[nearest][j]){dis[j] = dis[nearest]+G[nearest][j];
                    pre[j].clear();
                    pre[j].push_back(nearest);
                }else if(dis[j]==dis[nearest]+G[nearest][j]){pre[j].push_back(nearest);
                }
            }
        }
    } 
} 

int main(){scanf("%d %d %d %d",&Cmax,&N,&Sp,&M);
    for(int i=1;i<=N;++i){scanf("%d",&bikes_number[i]);
    }
    int a,b,time;
    for(int i=0;i<M;++i){scanf("%d %d %d",&a,&b,&time);
        G[a][b] = G[b][a] = time;
    }
    Dijkstra();
    DFS(Sp);// 从起点开始递归拜访
    printf("%d",min_need_sent_bike);
    for(int i=result.size()-1;i>=0;--i){printf("%d",result[i]);
        if(i>0) printf("->");
    }
    printf("%d",min_need_back_bike);
    return 0;
}