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

发布于：2025-06-03 ⋅ 阅读:(30) ⋅ 点赞:(0)

本文涉及知识点

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

小 C 与桌游

题目背景

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

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

3 2
1 2
1 3

样例输出 #1

3
2

提示

样例解释

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

计分方式

对于每一个测试点：

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

数据范围

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

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

对于 100 % 100\% 100% 的数据， 1 ≤ n , m ≤ 5 × 10 5 1 \le n, m \le 5 \times 10^5 1≤n,m≤5×105， 1 ≤ u , v ≤ n 1 \le u, v \le n 1≤u,v≤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 _DEBUG
	freopen("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);
		}

扩展阅读

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

视频课程

先学简单的课程，请移步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++**实现。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布