图论算法应用于P9487小熊游景点难题

未分类 3个月前程序员胖胖胖虎阿

135 0 0

文章标题：

图论算法在P9487小熊游览景点问题中的应用

文章内容：## 本文涉及的基础知识点

有关C++图论的知识链接：C++图论相关
C++深度优先搜索（DFS）的相关内容链接：C++DFS讲解
C++广度优先搜索（BFS）算法的相关链接：C++BFS算法剖析
此题目实际难度较高，比官网标注的难度至少高出一个层级，甚至可能高出两个层级

P9487 「LAOI-1」小熊游景点

题目描述

小熊的地图上存在 n 个景点，每个景点都有对应的分数 sᵢ。

有 n-1 对节点之间通过双向的公交线路直接相连，每条线路的收费为 wᵢ。

当下，小熊位于 a 景点，总司令处于 b 景点，他们需要沿着简单路径在 a 到 b 的路径上的 p 景点会合，之后再沿着简单路径一同前往 q 景点（q 为任意节点，且每个人不会重复游览 p 景点）。

针对 m 次询问，每次给定 a 和 b，需找出 p 和 q，使得在小熊与总司令花费之和最小的条件下，他们所经过的景点分数之和最大，并输出这个最大的分数之和（即小熊经过的景点分数之和加上总司令经过的景点分数之和）。需要注意的是，重复经过的线路的收费会被重复计算，重复经过的景点的分数也会被重复计算。

输入格式

第一行有两个整数 n 和 m，分别代表景点的数量以及询问的次数。

紧接着的一行包含 n 个整数，其中第 i 个整数对应第 i 个景点的权值 sᵢ。

随后的 n-1 行，每行包含三个整数 u、v 和 w，表示 u 节点和 v 节点之间存在一条收费为 w 的双向公交路线。

最后有 m 行，每行包含两个整数 a 和 b，代表小熊和总司令所在的景点位置。

输出格式

对于每一组询问，每行输出一个整数作为结果。

代码

template<class TSave>
class CMultMin {
public:
    CMultMin(const vector<int>& next, CParents& pars, const vector<TSave>& vals) :m_vNext(next), m_pars(pars) {
        const int N = next.size();
        const int M = pars.GetBitCnt();
        m_data.assign(N, vector<TSave>(M));
        for (int i = 0; i < N; i++) {
            m_data[i][0] = vals[i];
        }
        for (int i = 0; i + 1 < M; i++) {
            const int len = 1 << i;
            for (int j = 0; j < N; j++) {
                m_data[j][i + 1] = m_data[j][i];
                int j2 = pars.GetPow2Parent(j, i);
                if (-1 != j2) {
                    m_data[j][i + 1] = min(m_data[j][i], m_data[j2][i]);
                }
            }
        }
    }
    TSave Query(int cur, int len, TSave def) {
        for (int iBit = 0; iBit < m_data[0].size(); iBit++)
        {
            if (len & (1 << iBit))
            {
                def = min(def, m_data[cur][iBit]);
                cur = m_pars.GetPow2Parent(cur, iBit);
                if (-1 == cur) { return def; }
                len -= (1 << iBit);
            }
        }
        return def;
    };
    const vector<int>& m_vNext;
    vector<vector<TSave>> m_data;
    CParents& m_pars;
};

class Solution {
public:
    vector<long long> Ans(vector<int>& pw, vector<tuple<int, int, int>>& edge, vector<pair<int, int>>& que) {
        const int N = pw.size();
        vector<vector<int>> neiBo(N);
        for (auto& [n1, n2, w] : edge) {
            n1--, n2--;
        }
        for (auto& [a, b] : que) {
            a--, b--;
        }
        for (const auto& [n1, n2, w] : edge) {
            neiBo[n1].emplace_back(n2);
            neiBo[n2].emplace_back(n1);
        }
        auto leves = CBFSLeve::Leve(neiBo, { 0 });
        vector<int> pars(N, -1), ew(N);//pars[cur]记录cur父节点，ew[cur]记录边cur、pars[cur]的权。
        for (int i = 0; i < N; i++) {
            for (const auto& j : neiBo[i]) {
                if (leves[j] < leves[i]) { continue; }
                pars[j] = i;
            }
        }
        for (const auto& [n1, n2, w] : edge) {
            if (leves[n1] < leves[n2]) {
                ew[n2] = w;
            }
            else {
                ew[n1] = w;
            }
        }
        auto nodeByLeveSort = CBFSLeve::LeveSort(leves);
        vector<long long> pw0(pw.begin(), pw.end()), ew0(N);//d[i]记录i到0的简单路径的点权之和，e记录边权。
        for (const auto& node : nodeByLeveSort)
        {
            if (-1 == pars[node]) { continue; }
            pw0[node] += pw0[pars[node]];
            ew0[node] += ew0[pars[node]];
        }
        vector<vector<tuple<long long, long long, int>>> pc(N);
        vector<pair<long long, long long>> pp(N);
        for (int cur = 0; cur < N; cur++) {
            pp[cur] = make_pair(0, -pw[cur]);
            pc[cur].emplace_back(make_tuple(0, -pw[cur], -1));
        }
        for (auto it = nodeByLeveSort.rbegin(); it != nodeByLeveSort.rend(); ++it) {
            auto& v = pc[*it];
            if (v.size() > 1) {//只保留最优次优
                nth_element(v.begin(), v.begin() + 1, v.end());
                v.erase(v.begin() + 2, v.end());
            }
            const auto& t = pc[*it].front();
            if (-1 == pars[*it]) { continue; }
            pc[pars[*it]].emplace_back(make_tuple(get<0>(t) + ew[*it], get<1>(t) - pw[*it] - pw[pars[*it]], *it));
        }
        for (const auto& cur : nodeByLeveSort)
        {
            const int iPar = pars[cur];
            if (-1 == iPar) { continue; }
            auto t = make_pair(ew[cur] + get<0>(pp[iPar]), get<1>(pp[iPar]) - pw[iPar] - pw[cur]);
            pp[cur] = min(pp[cur], t);//经过父节点，不经过兄弟节点
            for (const auto& [f, s1, i] : pc[iPar]) {
                if ((-1 == i) || (i == cur)) { continue; }
                t = make_pair(get<0>(pc[i].front()) + ew[i] + ew[cur], get<1>(pc[i].front()) - pw[i] - 2 * pw[iPar] - pw[cur]);
                pp[cur] = min(pp[cur], t);//经过父节点，经过兄弟节点
                break;
            }
        }
        vector<pair<long long, long long>> ppc(N);
        for (int i = 0; i < N; i++) {
            ppc[i] = min(pp[i], make_pair(get<0>(pc[i].front()), get<1>(pc[i].front())));
        }
        C2Parents par2s(pars, leves);

        /*{
            vector<pair<long long, long long>> ppc1(N,make_pair(LLONG_MAX/2,0));
            for (int a = 0; a < N; a++) {
                for (int b = 0; b < N; b++) {
                    const int ab = par2s.GetPublicParent(a, b);
                    pair<long long, long long> abr(0,0);
                    for (int i = a; i != ab; i = pars[i]) {
                        abr.first += ew[i];
                        abr.second += -2 * pw[i];
                    }
                    for (int i = b; i != ab; i = pars[i]) {
                        abr.first += ew[i];
                        abr.second += -2 * pw[i];
                    }
                    abr.second += pw[a];
                    abr.second -= 2 * pw[ab];
                    ppc1[a] = min(ppc1[a], abr);
                }
            }
            for (int i = 0; i < N; i++) {
                AssertEx(-ppc1[i].second, ppc[i]);
            }
        };*/
        CMultMin<pair<long long, long long>> mult(pars, par2s, ppc);
        vector<long long> ans;
        for (const auto& [a, b] : que) {
            const int ab = par2s.GetPublicParent(a, b);
            const auto curAns1 = mult.Query(a, leves[a] - leves[ab], ppc[ab]);
            const auto curAns2 = mult.Query(b, leves[b] - leves[ab], ppc[ab]);
            const auto curAns3 = min(curAns1, curAns2);
            //AssertEx(curAns3, curAns);
            ans.emplace_back(pw0[a] + pw0[b] - 2 * pw0[ab] + pw[ab] - curAns3.second);
        }
        return ans;
    }
};

单元测试

vector<int> a;
vector<tuple<int, int, int>> edge;
vector<pair<int, int>> que;
TEST_METHOD(TestMethod1)
{
    a = { 1,1,1,1,1,1,1 },edge = { {1,2,3},{3,6,-4},{2,5,2},{1,3,6},{2,4,1},{3,7,5} },
        que = { {4,7} };
    auto res = Solution().Ans(a, edge,que);
    AssertV(vector<long long>{ 8 }, res);
}
TEST_METHOD(TestMethod12)
{
    a = { 786755,-687509,368192,154769,647117,-713535,337677,913223,-389809,-824004 },
        edge = { {1,2,-785875},{1,3,-77082},{1,4,-973070},{3,5,-97388},{2,6,-112274},{3,7,657757},{4,8,741733},{3,9,5656},{4,10,-35190} };
    que = { {3,3},{3,10},{7,3},{5,1},{2,10},{10,10},{1,6},{7,2},{8,9},{9,1} };
    auto res = Solution().Ans(a, edge, que);
    AssertV(vector<long long>{ 971424,- 1257332,1309101,3420605,-2313033,- 2567048, - 2467802,
        352646,759321,1368370 }, res);
}

扩展阅读

我想对大家说的一些话

工作中遇到问题时，可按类别查阅我的算法相关文章，点击查看《算法与数据汇总》。
学习算法时，建议按章节学习《喜缺全书算法册》，其中包含大量题目和测试用例，可通过打包下载获取。有效学习需具备明确目标、及时反馈以及处于难度合适的拉伸区，同时要保持专注。“闻缺陷则喜”是一种良好心态，尽早发现并解决问题能为老板节省成本。正如子墨子所言“事无终始，无务多业”，这也意味着专业的人应专注于专业之事。若把程序比作一条龙，那么算法便是它的眼睛。失败加上反思会走向成功，成功加上反思也会走向成功。

视频课程

若想先学习基础课程，可前往CSDN学院，聆听由白银讲师（即本人）讲解的课程。相关课程链接：https://edu.csdn.net/course/detail/38771
若希望快速提升能力以分担工作，可学习C#入职培训、C++入职培训等课程，相关讲师页面：https://edu.csdn.net/lecturer/6176