1018 Public Bike Management

dijkstra+DFS 处理多条单源最短路径相关问题的一般套路

第三篇模拟先鸽一下(

题面

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​3​​, we have 2 different shortest paths:

  1. PBMC -> S​1​​ -> S​3​​. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S​1​​ and then take 5 bikes to S​3​​, so that both stations will be in perfect conditions.
  2. PBMC -> S​2​​ -> S​3​​. 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−>S​1​​−>⋯−>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

本题类似于之前写过的 1003 Emergency 类似,都是在单源正权无向图的多条最短路径中进行选取,不同的是本题的选取规则相较于1003更为复杂:(本题题意为:在路径最短的情况下选择需要从PBMC中带去自行车数最少的,在带去自行车数最少的情况下选择带回PBMC的自行车数最少的,而1003的题意为在路径最短的情况下选择点权最大的),并且在找到符合条件的最短路径之后还要挨个儿节点对路径进行输出,这就需要另行设计了。我首先根据之前的解法写出了如下代码:

// 单用dijkstra的错误代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#define MAXN 100001
#define INFI 10000001
using namespace std;
struct edge
{
    int end;
    int value;
};
vector<edge> map[MAXN];
int vertex[MAXN];
int dis[MAXN];
int bring[MAXN]; // 在最短路径的情况下,第i个节点的需要带去的最小自行车数
int remain[MAXN]; // 在最短路径且需要带去的自行车数最小的情况下,需要带回的最小自行车数
bool vis[MAXN] = {false};
int cmax, n, sp, m;

void init()
{
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INFI;
    }
    for (int i = 0; i < map[0].size(); i++)
    {
        dis[map[0][i].end] = map[0][i].value;
        bring[map[0][i].end] = max(0, -vertex[map[0][i].end]);
        remain[map[0][i].end] = max(0, vertex[map[0][i].end]);
    }
}
void dijkstra()
{
    init();
    for (int i = 1; i <= n; i++)
    {
        int min = INFI;
        int mini = 0;
        for (int j = 1; j <= n; j++)
        {

            if (!vis[j] && min > dis[j])
            {
                min = dis[j];
                mini = j;
            }
        }
        vis[mini] = true;
        for (int j = 0; j < map[mini].size(); j++)
        {
            int t = map[mini][j].end;
            if (dis[t] > dis[mini] + map[mini][j].value)
            {
                dis[t] = dis[mini] + map[mini][j].value;

                bring[t] = bring[mini] + max(0, -(remain[mini] + vertex[t]));
                remain[t] = max(0, remain[mini] + vertex[t]);
            }
            else if (dis[t] == dis[mini] + map[mini][j].value)
            {
                if (bring[t] > bring[mini] + max(0, -(remain[mini] + vertex[t])))
                {
                    bring[t] = bring[mini] + max(0, -(remain[mini] + vertex[t]));
                    remain[t] = max(0, remain[mini] + vertex[t]);
                }
                else if (bring[t] == bring[mini] + max(0, -(remain[mini] + vertex[t])))
                {
                    if (remain[t] > max(0, remain[mini] + vertex[t]))
                    {
                        bring[t] = bring[mini] + max(0, -(remain[mini] + vertex[t]));
                        remain[t] = max(0, remain[mini] + vertex[t]);
                    }
                }
            }
        }
    }
}
void path()
{
    int c = sp;
    stack<int> s;
    while (c != 0)
    {
        s.push(c);
        for (int i = 0; i < map[c].size(); i++)
        {
            if (dis[map[c][i].end] + map[c][i].value == dis[c])
            {
                if (bring[map[c][i].end] + max(0, -(remain[map[c][i].end] + vertex[c])) == bring[c])
                {
                    if (max(0, remain[map[c][i].end] + vertex[c]) == remain[c])
                    {
                        c = map[c][i].end;
                    }
                }
            }
        }
    }
    cout << 0;
    while (!s.empty())
    {
        cout << "->" << s.top();
        s.pop();
    }
}

int main()
{
    cin >> cmax >> n >> sp >> m;
    vertex[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int l;
        cin >> l;
        vertex[i] = l - cmax / 2;
    }

    for (int i = 0; i < m; i++)
    {
        int index, end, value;
        edge e1;
        cin >> index >> end >> value;
        e1.end = end;
        e1.value = value;
        map[index].push_back(e1);
        edge e2;
        e2.end = index;
        e2.value = value;
        map[end].push_back(e2);
    }
    dijkstra();
    cout << bring[sp];
    cout << " ";
    path();
    cout << " ";
    if (remain[sp] > 0)
    {
        cout << remain[sp];
    }
    else
    {
        cout << 0;
    }

    return 0;
}

如上所示,和1003的解法一样,我将选择和更新符合要求的最短路径写进了dijkstra()算法的过程中,对于对最终选出的最短路径的输出我另写了一个path()函数来进行处理。

path()函数的原理为从Sp出发去不断寻找当前点在最优的最短路径的前驱点,由于题目中说所给的测试数据会保证这种最优性是唯一的,因此这个前驱点也一定是唯一的,所以只要将找到的前驱push()进一个栈,当到达源点(也就是PBMC)后说明已经完整找到了整条路径,此时再将这个栈中的元素倒出来进行输出就可以满足题目要求了。

但是在测试过程中我却有一个点一直过不去,我一开始以为是什么奇怪的边界值,尝试修改了一些条件还是过不了,万般无奈之下我翻开了《算法笔记》上机答案书,结果发现我的方法在原理上来说就是错误的。。。(我也不知道为什么只有一个点过不了。。只能说PAT的测试数据设计得有点emmmmmm迷惑?)

《算法笔记》上提供的一组上述方法过不了的测试数据为:

// input
10 4 4 5
4 8 9 0
0 1 1
1 2 1
1 3 2
2 3 1
3 4 1
// output
1 0->1->2->3->4 2

转化成图就是

按照我的代码给出的输出是

2 0->1->3->4 0

究其原因,是在S3点的更新中由于贪心选择了在较小的bring下选择了较小的remain,(当时1->3的bring值是1,remain值是3,而2->3的bring值是1,而remain值是7),从而在访问到S4点时出现了错误。注意到bring和remain的更新语句

if (bring[t] > bring[mini] + max(0, -(remain[mini] + vertex[t])))
{
    bring[t] = bring[mini] + max(0, -(remain[mini] + vertex[t]));
    remain[t] = max(0, remain[mini] + vertex[t]);
}

中,bring的取值是与remain有关的,而是否执行更新语句又取决于bring的值,所以如果我们用单纯的顺次贪心去更新这两个值就一定会得到错误的结果。

而1003那题能够通过只凭对dijkstra算法进行修改就可以解决这个问题的原因是点权的更新不会影响到线权的更新,因此单纯在dijkstra的过程中采取一种贪心的思路就可以得到正确的结果。

正确而普适的做法应当是:首先用标准的dijkstra()算法算好每一个点的dis[]值(这一阶段只关心dis),然后单独写一个DFS函数以Sp为根来搜索符合要求的最短路径(逆搜),并将搜索的过程中访问的节点保存到temp数组里(标答中用的是vector<int>来储存,区别不大)。
每当搜索到PBMC时,说明已经完整搜索到一条最短路径,此时逆向挨个访问保存起来的中间节点,并如第一种代码中所示的那样顺推出需要带去的自行车数forward和要带回的自行车数back(顺推),与保存起来的最小forward和最小back对比并更新。
注意一点,在DFS的过程中每当访问到一个节点,将其置入temp数组末尾,顺次访问其邻接点后要记得将这个元素从temp数组末尾取出(可以记做“在访问节点i的过程中temp数组末尾一直是i”)。由于这种做法类似于二叉树的后序遍历,使用非递归的方法可能比较难写,所以建议直接是采用递归的方法写(反正我非递归没写出来)。

正确的代码如下所示:

// Dijkstra算dis+DFS逆搜顺推
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#define MAXN 100001
#define INFI 10000001
using namespace std;
struct edge
{
    int end;
    int value;
};
vector<edge> map[MAXN];
int vertex[MAXN];
int dis[MAXN];
bool vis[MAXN] = {false};
int cmax, n, sp, m;

void init()
{
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INFI;
    }
    for (int i = 0; i < map[0].size(); i++)
    {
        dis[map[0][i].end] = map[0][i].value;
    }
}
void dijkstra()
{
    init();
    for (int i = 1; i <= n; i++)
    {
        int min = INFI;
        int mini = 0;
        for (int j = 1; j <= n; j++)
        {

            if (!vis[j] && min > dis[j])
            {
                min = dis[j];
                mini = j;
            }
        }
        vis[mini] = true;
        for (int j = 0; j < map[mini].size(); j++)
        {
            int t = map[mini][j].end;
            if (dis[t] >= dis[mini] + map[mini][j].value)
            {
                dis[t] = dis[mini] + map[mini][j].value;
            }
        }
    }
}
int minback = INFI, minforward = INFI;
vector<int> temp, path;
void DFS(int v)
{
    if (v == 0)
    {

        int f = 0, b = 0;
        for (int i = temp.size() - 1; i >= 0; i--)
        {
            int c = temp[i];
            f += max(0, -b - vertex[c]);
            b = max(0, b + vertex[c]);
        }
        if (f < minforward)
        {
            minforward = f;
            minback = b;
            path = temp;
        }
        else if (f == minforward)
        {
            if (b < minback)
            {
                minback = b;
                path = temp;
            }
        }
    }
    else
    {
        temp.push_back(v);
        for (int i = 0; i < map[v].size(); i++)
        {
            if (dis[v] == dis[map[v][i].end] + map[v][i].value)
            {
                DFS(map[v][i].end);
            }
        }
        temp.pop_back();
    }
}

int main()
{
    cin >> cmax >> n >> sp >> m;
    vertex[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int l;
        cin >> l;
        vertex[i] = l - cmax / 2;
    }

    for (int i = 0; i < m; i++)
    {
        int index, end, value;
        edge e1;
        cin >> index >> end >> value;
        e1.end = end;
        e1.value = value;
        map[index].push_back(e1);
        edge e2;
        e2.end = index;
        e2.value = value;
        map[end].push_back(e2);
    }
    dijkstra();
    DFS(sp);
    cout << minforward;
    cout << " 0";
    for (int i = path.size() - 1; i >= 0; i--)
    {
        cout << "->" << path[i];
    }
    cout << " ";
    cout << minback;
    return 0;
}

ok,大家晚安。

Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments