原題回顧

PAT_A1018原文鏈接

1018 Public Bike Management (30分)

作者: CHEN, Yue
單位: 浙江大學(xué)
時(shí)間限制: 400 ms
內(nèi)存限制: 64 MB
代碼長(zhǎng)度限制: 16 KB

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 S₃, we have 2 different shortest paths:
1.PBMC -> S₁ -> S₃. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S₁ and then take 5 bikes to S₃, so that both stations will be in perfect conditions.
2.PBMC -> S₂ -> S₃. 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: C_max(≤100), always an even number, is the maximum capacity of each station; N (≤500), the total number of stations; S_p, 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 C_i(i=1,?,N) where each C_iis the current number of bikes at S_i respectively. Then M lines follow, each contains 3 numbers: S_i, S_j, and T_ij which describe the time T_ij taken to move between stations S_i and S_j. 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?>S₁->...->S_p. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of S_p 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

解題思路及注意點(diǎn)

• 第一遍做時(shí)立馬就選擇了用Dijkstra算法解決諸如此類最短路徑類問(wèn)題(曾自學(xué)過(guò)算法筆記，對(duì)此印象比較深刻)纷捞，但是有一個(gè)問(wèn)題是無(wú)法在路徑中確定最優(yōu)解，只能把所有最短路徑確定后，再去選擇其中最優(yōu)的一條雷绢，所以必須在其中穿插DFS算法绳军，根據(jù)前驅(qū)結(jié)點(diǎn)遞歸來(lái)得到所有路徑坤检。
• 我對(duì)題目的第一個(gè)誤解是認(rèn)為從PBMC要么是往外帶，要么是往回帶埂陆，總之不會(huì)即帶出又帶回，這樣顯然多此一舉娃豹，按照這樣的思路寫出代碼后發(fā)現(xiàn)有兩個(gè)測(cè)試點(diǎn)未通過(guò)焚虱，于是又重新讀了幾遍題目，并經(jīng)過(guò)幾次不斷嘗試修改代碼(其實(shí)就是DFS部分)懂版，最后發(fā)現(xiàn)題目的設(shè)定是這樣的：假如路徑為 A->B->C->D鹃栽，如果在B點(diǎn)發(fā)現(xiàn)車輛不夠，需要補(bǔ)充躯畴，那么就必須要從始發(fā)地A多帶出缺少的車輛民鼓，無(wú)論此時(shí)C和D是什么狀態(tài)，即使C蓬抄、D全部爆滿丰嘉，也與A沒有關(guān)系，可以理解為一直向前走不回頭嚷缭，所以饮亏，如果目的地的車輛大于滿載的一半，那么無(wú)論前面的地點(diǎn)缺多少輛車，總會(huì)把目的地多余的車輛直接送回總部克滴，與路徑上的所有點(diǎn)無(wú)關(guān)逼争。 于是將代碼的DFS部分修改后順利通過(guò)了所有測(cè)試點(diǎn)。

代碼部分

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1010;
const int INF = 0x3fffffff;

int c, n, ed, m; //最大容量劝赔，頂點(diǎn)數(shù)誓焦，目的地，邊數(shù)
int G[maxn][maxn], d[maxn], weight[maxn]; //鄰接矩陣着帽，最短路徑杂伟，點(diǎn)權(quán)
vector<int> pre[maxn]; //前驅(qū)結(jié)點(diǎn)
vector<int> tempPath, Path; //當(dāng)前路徑，最優(yōu)路徑
bool vis[maxn]; //是否訪問(wèn)過(guò)
int minOut = INF, minBack = INF; //優(yōu)化結(jié)果

void Dijkstra(int s) //標(biāo)準(zhǔn)Dijkstra算法
{
    fill(d, d + maxn, INF);
    d[s] = 0;
    for (int i = 0; i <= n; i++) //因?yàn)榧由狭隧旤c(diǎn)仍翰，所以一共循環(huán)n+1次赫粥，每次都找到距離最短的點(diǎn)
    {
        int u = -1, MIN = INF; //u使d[u]最短
        for (int j = 0; j <= n; j++)
        {
            if (vis[j] == false && d[j] < MIN)
            {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) //找不到可達(dá)點(diǎn)，說(shuō)明搜索完畢
            return;
        vis[u] = true; //已訪問(wèn)
        for (int v = 0; v <= n; v++)
        {
            if (vis[v] == false && G[u][v] != INF) //未訪問(wèn)過(guò)且可到達(dá)
            {
                if (d[u] + G[u][v] < d[v])
                {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (d[u] + G[u][v] == d[v])
                {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

void DFS(int v)
{
    if (v == 0)
    {
        tempPath.push_back(v);
        int Out = 0, Back = 0; //需要帶出的車輛數(shù)目予借，需要帶回的車輛數(shù)目
        int take = 0; //路上搜集到的自行車數(shù)目
        for (int i = tempPath.size() - 1; i >= 0; i--)
        {
            int id = tempPath[i];
            if (weight[id] > (c / 2)) //超過(guò)一半越平，加入收集量
                take += weight[id] - (c / 2);
            if (weight[id] < (c / 2))
                take -= (c / 2) - weight[id]; //不足一半，用搜集量去彌補(bǔ)灵迫，不夠的話take變?yōu)樨?fù)值
            if (take < 0) // 一旦take為負(fù)說(shuō)明從起點(diǎn)到目前的結(jié)點(diǎn)需要從基地帶出才夠
            {
                Out += abs(take); //帶出的車輛累加
                take = 0; //從基地帶出車輛彌補(bǔ)負(fù)值的take秦叛，take置0
            }
        }
        if (take > 0) //到目的地后全部補(bǔ)充完畢仍有多余車輛
            Back = take; //帶回
        else
            Back = 0; // take<=0說(shuō)明不足或剛好夠，不用帶回
        if (Out < minOut) //優(yōu)化Out
        {
            Path = tempPath;
            minOut = Out;
            minBack = Back;
        }
        else if (Out == minOut && Back < minBack)
        {
            Path = tempPath;
            minOut = Out;
            minBack = Back;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++)
    {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}

int main()
{
    fill(G[0], G[0] + maxn * maxn, INF); //初始所有結(jié)點(diǎn)之間均不可達(dá)
    scanf("%d%d%d%d", &c, &n, &ed, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &weight[i]);
    }
    weight[0] = c / 2;
    int u, v;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &u, &v);
        scanf("%d", &G[u][v]);
        G[v][u] = G[u][v];
    }
    Dijkstra(0);
    DFS(ed);
    printf("%d ", minOut);
    for (int i = Path.size() - 1; i >= 0; i--)
    {
        printf("%d", Path[i]);
        if (i != 0)
            printf("->");
    }
    printf(" %d\n", minBack);
    return 0;
}

跨專業(yè)數(shù)據(jù)結(jié)構(gòu)初學(xué)者瀑粥，疏漏在所難免挣跋，歡迎指正～