【图论 拓扑排序 贪心 临项交换】P5603 小 C 与桌游 题解|普及+

本文涉及知识点

C++图论 拓扑排序
C++贪心 之临项交换

小 C 与桌游

题目背景

小 C 是一个热爱桌游的高中生，现在他被一个桌游难住了，快来帮帮他！

题目描述

这个桌游的地图可以被抽象成一个 $n$ 个点，$m$ 条边的有向无环图（不保证连通），小 C 在这个地图上行走，小 C 能走到某个点当且仅当能够到达这个点的所有点都已经被小 C 走到。小 C 会走到每个点恰好 $1$ 次，并且他能走到哪些点与他当前所在的点没有关系（即可以走到与当前所在的点没有连边的点，只要满足之前的条件）。

小 C 每走到一个标号比之前走到的点都大的点，他就会有 1 2 \\frac{1}{2} 21​ 的概率从对手那里拿到 $1$ 块筹码，有 1 2 \\frac{1}{2} 21​ 的概率给对手 $1$ 块筹码，双方初始各有 $1919810$ 个筹码。

小 C 的运气时好时坏，所以他希望你帮他计算出：

• 在最优情况下，即他每次都能从对手那里拿到筹码时，他采取最优的行走方式能得到的筹码数。
• 在最劣情况下，即对手每次都能从他那里拿到筹码时，他采取最优的行走方式会失去的筹码数。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示地图上有一条有向边 $(u,v)$，不保证无重边。

输出格式

输出两行，每行一个正整数，第一行表示最优情况下小 C 能拿到的筹码数，第二行表示最劣情况下小 C 会失去的筹码数。

样例 #1

样例输入 #1

3 21 21 3

样例输出 #1

32

提示

样例解释

最优情况下的行走方式是 $1-2-3$，最劣情况下的行走方式是 $1-3-2$。

计分方式

对于每一个测试点：

• 如果你输出格式错误或者两行都不正确，将会得到 $0$ 分。
• 如果你的输出第一行正确，第二行错误或第二行正确，第一行错误，将会得到这个测试点 $40\%$ 的分数。
• 否则，你将会得到这个测试点 $100\%$ 的分数。

数据范围

对于 $20\%$ 的数据，$1\le n,m\le 10$。

对于 $40\%$ 的数据，$1\le n,m\le 2000$。

对于 $100\%$ 的数据， 1≤n,m≤5× 10 5 1 \\le n, m \\le 5 \\times 10^5 1≤n,m≤5×105，$1\le u,v\le n$。

拓扑排序+贪心之临项交换

最优

可选点集：删除已经处理的点对应的边后，入度为0的点。
封装的模板的可选点集，出度为0的点。故将边都倒过来。
封装的拓扑排序，选取任意一点，本题最优时选择最小的点。将队列改成大根堆，就可以了。

最劣解

性质一：如果可选集中包括小于当前最大点的点，选取。不会失分。
性质二：如果没有，选取最大的点。

代码

核心代码

#include #include #include #include#include#include#include#include#include#include#include#include #include#include#include #include #include#include#include#include using namespace std;template<class T1, class T2>std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;}template<class T1, class T2, class T3 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;return in;}template<class T1, class T2, class T3, class T4 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;}template<class T = int>vector<T> Read() {int n;scanf(\"%d\", &n);vector<T> ret(n);for(int i=0;i < n ;i++) {cin >> ret[i];}return ret;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}class CTopSort1{public:template < class T = vector<int> >void Init(const vector<T>& vNeiBo, bool bDirect){const int iDelOutDeg = bDirect ? 0 : 1;m_c = vNeiBo.size();m_vBackNeiBo.resize(m_c);vector<int> vOutDeg(m_c);for (int cur = 0; cur < m_c; cur++){vOutDeg[cur] = vNeiBo[cur].size();for (const auto& next : vNeiBo[cur]){m_vBackNeiBo[next].emplace_back(cur);}}vector<bool> m_vHasDo(m_c);priority_queue<int, vector<int>, greater<int>> que;for (int i = 0; i < m_c; i++){if (vOutDeg[i] <= iDelOutDeg){m_vHasDo[i] = true;que.emplace(i);}}while (que.size()){const int cur = que.top();que.pop();OnDo(cur);for (const auto& next : m_vBackNeiBo[cur]){if (m_vHasDo[next]){continue;}vOutDeg[next]--;if (vOutDeg[next] <= iDelOutDeg){m_vHasDo[next] = true;que.emplace(next);}}};}int m_c;protected:virtual bool OnDo(int cur) = 0;vector<vector<int>> m_vBackNeiBo;};class CTopSortEx1 :public CTopSort1{public:virtual bool OnDo(int cur) override{m_ans += cur > m_pre;m_pre = max(cur,m_pre);return true;}int m_ans = 0, m_pre = -1;};class CTopSort2{public:template <class C = priority_queue<int, vector<int>, greater<int>>, class T = vector<int> >void Init(const vector<T>& vNeiBo, bool bDirect){const int iDelOutDeg = bDirect ? 0 : 1;m_c = vNeiBo.size();m_vBackNeiBo.resize(m_c);vector<int> vOutDeg(m_c);for (int cur = 0; cur < m_c; cur++){vOutDeg[cur] = vNeiBo[cur].size();for (const auto& next : vNeiBo[cur]){m_vBackNeiBo[next].emplace_back(cur);}}vector<bool> m_vHasDo(m_c);set<int> que;for (int i = 0; i < m_c; i++){if (vOutDeg[i] <= iDelOutDeg){m_vHasDo[i] = true;que.emplace(i);}}while (que.size()){int cur = *que.begin();if (cur > m_iMax) {cur = *que.rbegin();}que.erase(cur);OnDo(cur);for (const auto& next : m_vBackNeiBo[cur]){if (m_vHasDo[next]){continue;}vOutDeg[next]--;if (vOutDeg[next] <= iDelOutDeg){m_vHasDo[next] = true;que.emplace(next);}}};}int m_c;protected:virtual bool OnDo(int cur) = 0;vector<vector<int>> m_vBackNeiBo;int m_iMax = -1;};class CTopSortEx2 :public CTopSort2{public:virtual bool OnDo(int cur) override{m_ans += cur > m_iMax;m_iMax = max(cur, m_iMax);return true;}int m_ans = 0;};class Solution {public:pair<int,int> Ans(const int N,vector<pair<int, int>>& edge) {vector<vector<int>> neiBo(N);for (const auto& [from, to] : edge) {neiBo[to - 1].emplace_back(from - 1);}for (auto& v : neiBo) {sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}CTopSortEx1 ts;ts.Init(neiBo, true);CTopSortEx2 ts2;ts2.Init(neiBo, true);return{ ts.m_ans,ts2.m_ans };}};int main() {#ifdef _DEBUGfreopen(\"a.in\", \"r\", stdin);#endif // DEBUGint n,m;cin >> n >> m;auto edge = Read<pair<int,int>>(m);auto res = Solution().Ans(n,edge);cout << res.first << endl << res.second << endl;#ifdef _DEBUG/*printf(\"a0=%d\", a0);*///Out(h, \"h=\");#endif // DEBUGreturn 0;}

单元测试

int N;vector<pair<int, int>> edge;TEST_METHOD(TestMethod1){edge = { {1,2},{1,3} };auto res = Solution().Ans(3, edge);AssertEx({ 3,2 }, res);}TEST_METHOD(TestMethod2){edge = { {1,4},{2,1},{2,3} };auto res = Solution().Ans(4, edge);AssertEx({ 3,2 }, res);}TEST_METHOD(TestMethod3){edge = { {1,2},{1,3},{2,6},{3,5},{5,4} };auto res = Solution().Ans(6, edge);AssertEx({ 5,3 }, res);}

扩展阅读

我想对大家说的话 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 如果程序是一条龙，那算法就是他的是睛 失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。