【二分查找 并集查找】P6004 [USACO20JAN] Wormhole Sort S|普及+

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

本文涉及的基础知识点

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

输出 #1

9

输入输出样例 #2

输入 #2

4 1
1 2 3 4
4 2 13

输出 #2

-1

说明/提示

样例解释 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]到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++**实现。

网站公告

今日签到

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

热门文章

最新发布