当前位置：首页 > java >正文

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

java 2025/7/13 14:45:33

本文涉及知识点

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

小 C 与桌游

题目背景

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

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

3 2
1 2
1 3

样例输出 #1

3
2

提示

样例解释

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

计分方式

对于每一个测试点：

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

数据范围

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

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

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

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

最优

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

最劣解

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

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
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 // DEBUG	int 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 // DEBUG		return 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);}

扩展阅读

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