【PAT】Public Bike Management

问题描述

杭州市提供公共自行车服务，为来自世界各地的游客提供便利。人们可以在任何车站租一辆自行车，然后将车返回城市的任何其他车站。公共自行车管理中心（PBMC）持续监控所有车站的实时容量。如果一个站点正好是半满的话，那么它就处于完美状态。如果站点已满或空，PBMC将收集或发送自行车以调整该站点的状况以完善。此外，路上的所有站点也将进行调整。
报告问题站时，PBMC将始终选择到达该站的最短路径。如果有多个最短路径，则将选择从PBMC发送的自行车数量最少的路径。

输入

第一行：Cmax（每个占的最大容量），N（站的个数），Sp（问题站的索引），M（道路的数量）
第二行：包含N个非负数Ci（i = 1，... N），其中每个Ci分别是Si的当前自行车数
之后M行：每行包含3个数字：Si，Sj和Tij，Tij表示在站点Si和Sj之间移动的时间Tij

输出：

将结果打印在一行中。首先输出PBMC必须发送的自行车数量。然后在一个空格之后，以下列格式输出路径：0-> S1 - > ...-> Sp。最后， 在一个空格后输出在Sp的条件调整到完美后我们必须带回PBMC的自行车数量。

解题思路

采用dfs求出0到sp的路径，比较选出最优的路径。
利用二维矩阵存储图，用给一个一维数组存储站点的自行车数。

代码

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
vector<bool> marked;
vector<int>path,minpath;
int cost=0,mincost=100,minIn=100,minOut=100;
int cmax;

void dfs(int start, int cur, int sp, vector<int> &nodes,vector<vector<int> > &graph) {
    marked[cur] = true;
    path.push_back(cur);
    cost += graph[start][cur];

    int inBike = 0, outBike = 0;//inbike为要带回去的车，outbike为要带去的车。
    if (cur == sp) {
       // cout<<"cur:"<<cur<<endl;
        for (int i = 1; i <path.size(); i++) {
            if (nodes[path[i]] > cmax / 2) {
                inBike += nodes[path[i]] - cmax / 2;
            }
            else if(cmax/2- nodes[path[i]]<inBike){
                inBike -= (cmax / 2 - nodes[path[i]]);

            }
            else {
                outBike += (cmax / 2 - nodes[path[i]]) - inBike;
                inBike = 0;
            }

        }
        //判断路径是否更好；
        if(cost!=mincost){
            if (cost < mincost) {
                mincost = cost;
                minpath = path;
                minIn = inBike;
                minOut = outBike;
            }
        }else if (outBike != minOut) {
            if (outBike<minOut) {
                minpath = path;
                minIn = inBike;
                minOut = outBike;

            }
        }
        else if (inBike < minIn) {
            minpath = path;
            minIn = inBike;
            minOut = outBike;
        }

    }

    else {
        for (int i = 1; i <nodes.size(); i++) {
            if(graph[cur][i]!=0&&!marked[i]){
                dfs(cur, i,sp, nodes, graph);
            }
        }
    }
    marked[cur] = false;
    path.pop_back();
    cost -= graph[start][cur];


}



int main() {
    int  N, Sp, M;
    cin >> cmax >> N >> Sp >> M;
    marked.resize(N + 1, false);
    vector<int>nodes(N + 1, 0);
    vector<vector<int> >graph(N+1,vector<int>(N+1,0));
    for (int i = 1; i <= N; i++) {//每个站点的权值
        cin >> nodes[i];
    }
    int m, n,t;
    for (int i = 0; i < M; i++) {//得到图
        cin >> m >> n >> t;
        graph[m][n] = t;
        graph[n][m] = t;
    }
    dfs(0, 0, Sp, nodes, graph);
    cout << minOut << " 0";
    for (int i = 1; i < minpath.size(); i++) {
        cout << "->" << minpath[i];
    }
    cout << " " << minIn << endl;

    return 0;
}