本文涉及的底子知识点
C++二分查找
C++图论
并集查找
P6004 [USACO20JAN] Wormhole Sort S
题目描述
Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序脱离牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。
今天早上，如同往常一样，Farmer John 的 N N N 头编号为 1 … N 1 \ldots N 1…N 的奶牛（ 1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^5 1≤N≤105）
;，分散在牛棚中 N N N 个编号为 1 … N 1 \ldots N 1…N 的不同位置，奶牛 i i i 位于位置 p i p_i pi。但是今天早上还出现了 M M M 个编号为 1 … M 1 \ldots M 1…M 的虫洞（ 1 ≤ M ≤ 1 0 5 1 \leq M \leq 10^5 1≤M≤105）
;，其中虫洞 i i i 双向连接了位置 a i a_i ai 和 b i b_i bi，宽度为 w i w_i wi（ 1 ≤ a i , b i ≤ N , a i ≠ b i , 1 ≤ w i ≤ 1 0 9
1\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^9
1≤ai,bi≤N,ai=bi,1≤wi≤109
）
;。
在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞互换位置。奶牛们必要反复进行如许的互换，直到对于 1 ≤ i ≤ N 1 \leq i \leq N 1≤i≤N，奶牛 i i i 位于位置 i i i。
奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。包管奶牛们有可能排好序。
输入格式
输入的第一行包含两个整数 N N N 和 M M M。
第二行包含 N N N 个整数 p 1 , p 2 , … , p N p_1,p_2,\ldots ,p_N p1,p2,…,pN。包管 p p p 是 1 … N 1 \ldots N 1…N 的一个分列。
对于 1 1 1 到 M M M 之间的每一个 i i i，第 i + 2 i+2 i+2 行包含整数 a i , b i , w i a_i,b_i,w_i ai,bi,wi。
输出格式
输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不必要用任何虫洞来排序，输出 − 1 -1
−1。
输入输出样例 #1
输入 #1
- 4 4
- 3 2 1 4
- 1 2 9
- 1 3 7
- 2 3 10
- 2 4 3
输入输出样例 #2
输入 #2
输出 #2
阐明/提示
样例表明 1
以下是一个仅用宽度至少为 9
的虫洞给奶牛排序的可能方案：
- 奶牛 1 和奶牛 2 利用第三个虫洞互换位置。
- 奶牛 1 和奶牛 3 利用第一个虫洞互换位置。
- 奶牛 2 和奶牛 3 利用第三个虫洞互换位置。
子任务
- 测试点 3 ∼ 5 3 \sim 5 3∼5 满足 N , M ≤ 1000 N,M \leq 1000 N,M≤1000。
- 测试点 6 ∼ 10 6 \sim 10 6∼10 没有额外限定。
[USACO20JAN] Wormhole Sort S
典型的最小值最大化。
边p到i组成的有向图G。有如下性质：
性质一：出度、入度都是1。出发地和目标地一一对应，恣意出发地只有一头牛，恣意目标地只有一头牛到达。
性质二：恣意点都在环上。否则无法出度和入度都不是0。
性质三：环之间不连通，或者出度或入度大于1。
不失一样平常性，假定某个环依次是：i1,i2,i3,i4。
如果本题有解，i1通过多少个虫洞必须能到达i2，i2到i3,i3到i4,i4到i1也是。即i1,i2,i3,i4在同一个连通地区。
如果i1,i2,i3,i4在一个连通地区，则i1能到到达i2,i2能够到达i3,i3能够到达i4,i4能够到达i1。
本题 ⟺ \iff ⟺ 将宽度大于等于mid的虫洞连通后，i1,i2,i3,i4在一个联通地区。
二分之，二分类型：探求尾端。
参数范围：[1,虫洞的最大宽度]
如果初始状态下，都是自环，即n个连通地区，则返回-1
。
代码
核心代码
- #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; 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 KMP{public: virtual int Find(const string& s, const string& t) { CalLen(t); for (int i1 = 0, j = 0; i1 < s.length(); ) { for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++); //i2 = i1 + j 此时s[i1,i2)和t[0,j)相称 s[i2]和t[j]不存在或相称 //t[0,j)的结尾索引是j-1
- ，以是最长公共前缀为m_vLen[j-1
- ]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2) if (0 == j) { i1++; continue; } const int i2 = i1 + j; j = m_vLen[j - 1]; i1 = i2 - j;//i2不变 } return -1
- ; } //vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增长可调试性 部分m_vSameLen[i]会缺失 //static vector<int> Next(const string& s) //{// j = vNext[i] 表现s[0,i]的最大公共前后缀是s[0,j] // const int len = s.length(); // vector<int> vNext(len, -1
- ); // for (int i = 1; i < len; i++) // { // int next = vNext[i - 1]; // while ((-1
- != next) && (s[next + 1] != s[i])) // { // next = vNext[next]; // } // vNext[i] = next + (s[next + 1] == s[i]); // } // return vNext; //} const vector<int> CalLen(const string& str) { m_vLen.resize(str.length()); for (int i = 1; i < str.length(); i++) { int next = m_vLen[i - 1]; while (str[next] != str[i]) { if (0 == next) { break; } next = m_vLen[next - 1]; } m_vLen[i] = next + (str[next] == str[i]); } return m_vLen; }protected: int m_c; vector<int> m_vLen;//m_vLen[i] 表现str[0,i]的最长公共前后缀的长度};class CUnionFind{public: CUnionFind(int iSize) :m_vNodeToRegion(iSize) { for (int i = 0; i < iSize; i++) { m_vNodeToRegion[i] = i; } m_iConnetRegionCount = iSize; } CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size()) { for (int i = 0; i < vNeiBo.size(); i++) { for (const auto& n : vNeiBo[i]) { Union(i, n); } } } int GetConnectRegionIndex(int iNode) { int& iConnectNO = m_vNodeToRegion[iNode]; if (iNode == iConnectNO) { return iNode; } return iConnectNO = GetConnectRegionIndex(iConnectNO); } void Union(int iNode1, int iNode2) { const int iConnectNO1 = GetConnectRegionIndex(iNode1); const int iConnectNO2 = GetConnectRegionIndex(iNode2); if (iConnectNO1 == iConnectNO2) { return; } m_iConnetRegionCount--; if (iConnectNO1 > iConnectNO2) { UnionConnect(iConnectNO1, iConnectNO2); } else { UnionConnect(iConnectNO2, iConnectNO1); } } bool IsConnect(int iNode1, int iNode2) { return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2); } int GetConnetRegionCount()const { return m_iConnetRegionCount; } vector<int> GetNodeCountOfRegion()//各联通地区的节点数量 { const int iNodeSize = m_vNodeToRegion.size(); vector<int> vRet(iNodeSize); for (int i = 0; i < iNodeSize; i++) { vRet[GetConnectRegionIndex(i)]++; } return vRet; } std::unordered_map<int, vector<int>> GetNodeOfRegion() { std::unordered_map<int, vector<int>> ret; const int iNodeSize = m_vNodeToRegion.size(); for (int i = 0; i < iNodeSize; i++) { ret[GetConnectRegionIndex(i)].emplace_back(i); } return ret; }private: void UnionConnect(int iFrom, int iTo) { m_vNodeToRegion[iFrom] = iTo; } vector<int> m_vNodeToRegion;//各点地点联通地区的索引,本联通地区恣意一点的索引，为了增长可明确性，用最小索引 int m_iConnetRegionCount;};template<class INDEX_TYPE>class CBinarySearch{public: CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex, INDEX_TYPE tol = 1) :m_iMin(iMinIndex), m_iMax(iMaxIndex), m_iTol(tol) {} template<class _Pr> INDEX_TYPE FindFrist(_Pr pr) { auto left = m_iMin - m_iTol; auto rightInclue = m_iMax; while (rightInclue - left > m_iTol) { const auto mid = left + (rightInclue - left) / 2; if (pr(mid)) { rightInclue = mid; } else { left = mid; } } return rightInclue; } template<class _Pr> INDEX_TYPE FindEnd(_Pr pr) { INDEX_TYPE leftInclude = m_iMin; INDEX_TYPE right = m_iMax + m_iTol; while (right - leftInclude > m_iTol) { const auto mid = leftInclude + (right - leftInclude) / 2; if (pr(mid)) { leftInclude = mid; } else { right = mid; } } return leftInclude; }protected: const INDEX_TYPE m_iMin, m_iMax, m_iTol;};class Solution {public: int Ans(vector<int>& vp, vector<tuple<int, int, int>>& edge) { const int N = vp.size(); CUnionFind uf(N); for (int i = 0; i < N; i++) { uf.Union(vp[i] - 1, i); } if (uf.GetConnetRegionCount() == N) { return -1
- ; } auto m = uf.GetNodeOfRegion(); auto Check = [&](int mid) { CUnionFind uf2(N); for (const auto& [u, v, w] : edge) { if (w < mid) { continue; } uf2.Union(u - 1, v - 1); } for (const auto& [tmp, v] : m) { for (int i = 1; i < v.size(); i++) { if (!uf2.IsConnect(v[0], v[i])) { return false; } } } return true; }; return CBinarySearch<int>(1, 1e9
- ).FindEnd(Check); }};int main() {#ifdef _DEBUG freopen("a.in", "r", stdin);#endif // DEBUG ios::sync_with_stdio(0); int n,m; cin >> n >> m; auto vp = Read<int>(n); auto edge = Read<tuple<int, int, int>>(m);#ifdef _DEBUG //printf("M=%d", m); Out(vp, ",vp="); Out(edge, "v="); //Out(edge2, ",edge2="); /*Out(que, "que=");*/#endif // DEBUG auto res = Solution().Ans(vp,edge); cout << res << "\n"; return 0;}
- vector<int> vp ; vector<tuple<int, int, int>> edge; TEST_METHOD(TestMethod11) { vp = { 3,2,1,4 },edge = { {1,2,9
- },{1,3,7},{2,3,10},{2,4,3} }; auto res = Solution().Ans(vp,edge); AssertEx(9
- , res); } TEST_METHOD(TestMethod12) { vp = { 1,2,3,4 }, edge = { {4,2,13} }; auto res = Solution().Ans(vp, edge); AssertEx(-1
- , 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++**实现。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
