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

【拓扑排序】P2403 [SDOI2010] 所驼门王的宝藏|省选-

news 2025/7/31 7:28:13

本文设计知识点

C++图论拓扑排序

P2403 [SDOI2010] 所驼门王的宝藏

题目描述

在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的 AlpacaL.Sotomon 是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天 Henry Curtis 故事的起点。Henry 是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状，由 $\times C$ 间矩形宫室组成，其中有 $N$ 间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这 $N$ 间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种：

“横天门”：由该门可以传送到同行的任一宫室；
“纵寰门”：由该门可以传送到同列的任一宫室；
“任意门”：由该门可以传送到以该门所在宫室为中心周围 $8$ 格中任一宫室（如果目标宫室存在的话）。

深谋远虑的 Henry 当然事先就搞到了所驼门王当年的宫殿招标册，书册上详细记录了每扇传送门所属宫室及类型。而且，虽然宫殿内外相隔，但他自行准备了一种便携式传送门，可将自己传送到殿内任意一间宫室开始寻宝，并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次，且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制，每间宫室也可以多次出入。

现在 Henry 已经打开了便携门，即将选择一间宫室进入。为得到尽多宝藏，他希望安排一条路线，使走过的不同藏宝宫室尽可能多。请你告诉 Henry 这条路线最多行经不同藏宝宫室的数目。

输入格式

第一行给出三个正整数 $N, R, C$ 。

以下 $N$ 行，每行给出一扇传送门的信息，包含三个正整数 $x_i,y_i,T_i$ ，表示该传送门设在位于第 $x_i$ 行第 $y_i$ 列的藏宝宫室，类型为 $T_i$ 。 $T_i$ 是一个 $\sim 3$ 间的整数， $1$ 表示可以传送到第 $x_i$ 行任意一列的“横天门”， $2$ 表示可以传送到任意一行第 $y_i$ 列的“纵寰门”， $3$ 表示可以传送到周围 $8$ 格宫室的“任意门”。

保证 $\le x_i \le R$ ， $\le y_i \le C$ ，所有的传送门位置互不相同。

输出格式

输出只有一个正整数，表示你确定的路线所经过不同藏宝宫室的最大数目。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据规模和约定：

样例一图解

红色、绿色、蓝色表示3种门。第一张图表示所有路线，第二张图表示最优解。
在这里插入图片描述

拓扑排序离算化

本题本质是求，缩点后最长链。
性质一：一定存在最优解不经过“没有宝藏的宫室”，因为它没有传送门，故只能在终点。如果在终点，且不会获得宝藏，故删除也不影响。
性质二：相同行的横向门可以统一处理。第一个横向门，单向边连本行所有的门。第i个横向门，双向连第i-1个横向门。

实现

哈希映射（或有序映射)mCode记录各有宝物的单元格的编码。
rs[r]记录第r行所有有宝物的单元格，rdoor[r]第r行所有的横向门。
cs[c]记录第c列所有宝物的单元格，cdoor[c]第c列所有的纵向门。
按性质二，处理横向门。
类似性质三处理纵向门。
处理任意门。
缩点
求最长链。

代码

核心代码

#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 T1, class T2, class T3, class T4,class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5,class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5,T6>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>get<5>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}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;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class CDGTopSort
{
public:template <class T = vector<int> >CDGTopSort(const vector<T>& vNeiBo) :m_vDeg(vNeiBo.size()), m_neiBo(vNeiBo) {const int N = vNeiBo.size();m_backNeiBo.resize(N);for (int cur = 0; cur < N; cur++){m_vDeg[cur] = vNeiBo[cur].size();for (const auto& next : vNeiBo[cur]){m_backNeiBo[next].emplace_back(cur);}}}void Init() {auto Add = [&](int i) {if (0 != m_vDeg[i]) { return; }m_que.emplace(i);};for (int i = 0; i < m_vDeg.size(); i++){Add(i);}while (m_que.size()){const int cur = m_que.front(); m_que.pop();if (!OnDo(cur)) { continue; }for (const auto& next : m_backNeiBo[cur]){m_vDeg[next]--;Add(next);}};}queue<int> m_que;vector<int> m_vDeg;vector<int> m_vSort;
protected:const vector<vector<int>>& m_neiBo;vector<vector<int>> m_backNeiBo;virtual bool OnDo(int cur) {m_vSort.emplace_back(cur);return true;};
};class CNeiBo
{
public:static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& [i1, i2] : edges){vNeiBo[i1 - iBase].emplace_back(i2 - iBase);if (!bDirect){vNeiBo[i2 - iBase].emplace_back(i1 - iBase);}}return vNeiBo;}static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, const vector<tuple<int, int, int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& [u, v, w] : edges){vNeiBo[u - iBase].emplace_back(v - iBase, w);if (!bDirect){vNeiBo[v - iBase].emplace_back(u - iBase, w);}}return vNeiBo;}static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};class CSCCTarjan {
public:CSCCTarjan(vector<vector<int>>& neiBo) :m_neiBo(neiBo) {const int N = neiBo.size();m_vTime.assign(N, -1);m_vBack.assign(N, -1);m_vIsStack.assign(N, false);for (int i = 0; i < N; i++) {DFS(i);}}void InitPtNew() {m_ptNew.resize(m_neiBo.size());iota(m_ptNew.begin(), m_ptNew.end(), 0);for (auto& v : m_sccs) {nth_element(v.begin(), v.begin(), v.end());m_v0.emplace_back(v[0]);for (int i = 1; i < v.size(); i++) {m_ptNew[v[i]] = v[0];}}}vector<vector<int>> GetNewNeiBo() {vector<vector<int>> neiBo(m_neiBo.size());for (int i = 0; i < neiBo.size(); i++) {const int n1 = m_ptNew[i];for (const auto& next : m_neiBo[i]) {const int n2 = m_ptNew[next];if (n1 == n2) { continue; }//自环neiBo[n1].emplace_back(n2);}}for (int i = 0; i < neiBo.size(); i++) {unordered_set<int> s(neiBo[i].begin(), neiBo[i].end());vector<int> tmp(s.begin(), s.end());neiBo[i].swap(tmp);}return neiBo;}vector<vector<int>> m_sccs;vector<int> m_v0, m_ptNew;
protected:void DFS(int cur) {if (-1 != m_vTime[cur]) { return; }m_vTime[cur] = m_vBack[cur] = m_iTimes++;m_vIsStack[cur] = true;m_sta.emplace(cur);for (const auto& next : m_neiBo[cur]) {if (-1 == m_vTime[next]) {DFS(next);m_vBack[cur] = min(m_vBack[cur], m_vBack[next]);}else if (m_vIsStack[next]) {m_vBack[cur] = min(m_vBack[cur], m_vTime[next]);}}if (m_vTime[cur] != m_vBack[cur]) { return; }vector<int> scc;while (m_sta.size()){auto u = m_sta.top(); m_sta.pop();scc.emplace_back(u);m_vIsStack[u] = false;if (cur == u) { break; }}m_sccs.emplace_back(scc);}vector<vector<int>>& m_neiBo;int  m_iTimes = 0;vector<int> m_vTime, m_vBack;vector<bool> m_vIsStack;stack<int> m_sta;
};class Solution {
public:int Ans(const int R, const int C, vector<tuple<int, int, int>>& edge) {const int N = edge.size();vector<int> pw(N);vector<vector<int>> neiBo;{map<pair<int, int>, int> mCode;vector<vector<int>> rs(R + 1), rrooms(R + 1), cs(C + 1), crooms(C + 1);vector<pair<int, int>> edge3;for (const auto& [r, c, kind] : edge) {const int iCode = mCode.size();mCode[make_pair(r, c)] = iCode;rs[r].emplace_back(iCode);cs[c].emplace_back(iCode);if (1 == kind) {rrooms[r].emplace_back(iCode);}else if (2 == kind) {crooms[c].emplace_back(iCode);}else {edge3.emplace_back(r, c);}}vector<vector<int>> neiBo1(N);for (int r = 1; r <= R; r++) {if (0 == rrooms[r].size()) { continue; }for (int j = 1; j < rrooms[r].size(); j++) {neiBo1[rrooms[r][0]].emplace_back(rrooms[r][j]);neiBo1[rrooms[r][j]].emplace_back(rrooms[r][0]);}for (auto& code : rs[r]) {neiBo1[rrooms[r][0]].emplace_back(code);}}for (int c = 1; c <= C; c++) {if (0 == crooms[c].size()) { continue; }for (int j = 1; j < crooms[c].size(); j++) {neiBo1[crooms[c][0]].emplace_back(crooms[c][j]);neiBo1[crooms[c][j]].emplace_back(crooms[c][0]);}for (const auto& code : cs[c]) {neiBo1[crooms[c][0]].emplace_back(code);}}for (const auto& [r, c] : edge3) {for (int r1 = r - 1; r1 <= r + 1; r1++) {for (int c1 = c - 1; c1 <= c + 1; c1++) {if ((r == r1) && (c == c1)) { continue; }if (0 == mCode.count(make_pair(r1, c1))) { continue; }neiBo1[mCode[make_pair(r, c)]].emplace_back(mCode[make_pair(r1, c1)]);}}}CSCCTarjan scc(neiBo1);scc.InitPtNew();for (const auto& v : scc.m_sccs) {for (const auto& i : v) {pw[i] = v.size();}}neiBo = scc.GetNewNeiBo();assert(mCode.size() == N);}vector<int> ans(N, -1);function<void(int)>DFS = [&](int cur) {if (-1 != ans[cur]) { return; }ans[cur] = pw[cur];for (const auto& next : neiBo[cur]) {DFS(next);ans[cur] = max(ans[cur], ans[next] + pw[cur]);}};for (int i = 0; i < N; i++) {DFS(i);}return *max_element(ans.begin(), ans.end());}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	int N,R,C;cin >> N >> R >> C;auto edge = Read<tuple<int, int,int>>(N);
#ifdef _DEBUGprintf("R=%d,C=%d",R,C);Out(edge, ",edge=");//Out(que, ",que=");
#endif // DEBUGauto res = Solution().Ans(R,C, edge);cout << res << "\n";return 0;
}

单元测试

int R,C;vector<tuple<int, int,int>> edge;TEST_METHOD(TestMethod01){R = 7, C = 7, edge = { {2,2,1},{2,4,2},{1,7,2},{2,7,3},{4,2,2},{4,4,1},{6,7,3},{7,7,1},{7,5,2},{5,2,1} };auto res = Solution().Ans(R, C, edge);AssertEx(9, res);}

扩展阅读

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