pat 1018 Public Bike Management

题意有三：1.时间最短 2.送出车辆最少 3.回收车辆最少

陷阱有一：调整路径上站点的车辆数目时，不能把后面站点多出来的车辆返补回前面车辆数不够的站点。乍看之下这是符合逻辑的，因为在前面的站点的时候不能知道后面的站点是什么情况，所以按理应该逐个调整合理，后面的站点影响不到前面的调整。但是细想之后发现这其实是很死板的做法，现实当中设计这样一个管理系统肯定能够实时收集每个站点的自行车数，所以在出发前应该就能得出这条路径上总的自行车数目，继而就能得到最优的送出数。但四十是介样子素通不过滴。

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define MAX 501
#define INF 0x6FFFFFFF

using namespace std;

struct Path
{//路径
    vector<int> station;//路径上的站点
    int sent;//该路径需要送出的车辆数
    int back;//需要带回的车辆数
};

int map[MAX][MAX];//是否连通
int visited[MAX];//访问标志
int bikes[MAX], dist[MAX];//站点车辆和从PMBC到该站点的最短路径
vector<Path> path;
Path pathTemp;

bool compare(Path p1, Path p2)
{//路径比较，按照送出数和归还数
    if(p1.sent<p2.sent)
        return true;
    else if(p1.sent==p2.sent && p1.back<p2.back)
        return true;
    else
        return false;
}

void Init()
{//初始化状态
    for(int i=0; i<MAX; i++)
    {
        visited[i] = 0;
        dist[i] = INF;
        for(int j=0; j<MAX; j++)
            map[i][j] = 0;
    }
}

void Dijkstra(int node, int n)
{//node 为起始节点，n为节点数
    for(int i=0; i<n; i++)
        dist[i] = INF;//初始距离均设为无穷大

    dist[node] = 0;//起始节点距离为0

    for(;;)
    {
        int min = INF;
        int num = -1;
        for(int i=0; i<n; i++)
        {//找到现存未知的距离最小的节点
            if(dist[i]<=min && visited[i] == 0)
            {    min = dist[i];    num = i;}
        }

        if(num == -1)
            break;

        visited[num] = 1;//将该节点标为已知
        for(int i=0; i<n; i++)
        {
            if(!visited[i] && map[i][num]!=0 )
            //更新相邻节点路径
                if(dist[i] > dist[num]+ map[num][i])
                    dist[i] = dist[num] + map[num][i];
        }
    }
}

void DFS(int station, int dest, int _dist, int n)
{//当前站点，目标站点，路径，总站点数
    visited[station] = 1;
    if(station!=0)
        pathTemp.station.push_back(station);//路径更新
    if(station == dest)
    {
        if(_dist == dist[dest]) //到达站点且距离满足dijkstra找到的最短距离
            path.push_back(pathTemp);
        return;
    }

    if(_dist>dist[dest])
        return;

    for(int i=0; i<n; i++)
    {
        if(!visited[i] && map[station][i]!=0)
        {    
            DFS(i, dest, _dist + map[station][i], n);
            pathTemp.station.pop_back();//回调，弹出节点，避免重复写入
            visited[i] = 0;
        }
    }
}

int main(void)
{
    //ifstream fin("data.txt");

    int bikeMax, stationNum, problemStation, roadNum;
    cin>>bikeMax>>stationNum>>problemStation>>roadNum;
    Init();//初始化

    for(int i=1; i<stationNum+1; i++)
        cin>>bikes[i];
    for(int i=0; i<roadNum; i++)
    {
        int station1, station2, time;
        cin>>station1>>station2>>time;
        map[station1][station2] = time;
        map[station2][station1] = time;
    }

    Dijkstra(0, stationNum+1);//寻求最优路径

    for(int i=0; i<stationNum+1; i++)//访问标志复原
        visited[i] = 0;

    DFS(0, problemStation, 0, stationNum+1);

    //计算每个时间最优路径下需要送出和带回的自行车数
    int extra;
    for(int i=0; i<path.size(); i++)
    {
        extra = 0;//从路径上前面站点带来的多余车辆
        for(int j=0; j<path[i].station.size(); j++)
        {
            if(bikes[path[i].station[j]]<bikeMax/2)
            {
                if(extra>=bikeMax/2 - bikes[path[i].station[j]])
                    extra -= bikeMax/2 - bikes[path[i].station[j]];
                else
                {    
                    path[i].sent += bikeMax/2 - bikes[path[i].station[j]] - extra;    
                    extra = 0;
                }
            }
            if(bikes[path[i].station[j]]>bikeMax/2)
                extra += bikes[path[i].station[j]] - bikeMax/2;
        }
        path[i].back = extra;
    }

    sort(path.begin(), path.end(), compare);//按照少送出，少带回的原则排序

    cout<<path[0].sent<<" "<<0;
    for(int i=0; i<path[0].station.size(); i++)
        cout<<"->"<<path[0].station[i];
    cout<<" "<<path[0].back;
    return 0;
}

pat 1018 Public Bike Management

推荐阅读