【并集查找启发性合并】P8710 [蓝桥杯 2020 省 AB1] 网络分析|普及+

闻缺陷则喜何志丹

1692人浏览 · 2025-05-29 07:00:00

闻缺陷则喜何志丹 · 2025-05-29 07:00:00 发布

本文涉及的基础知识点

C++图论
 C++并集查找预计2025年5月29号 7:00发布启发式合并

P8710 [蓝桥杯 2020 省 AB1] 网络分析

题目描述

小明正在做一个网络实验。

他设置了 $n$ 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

输入格式

输入的第一行包含两个整数 $n$ ， $m$ ，分别表示节点数量和操作数量。节点从 $1$ 至 $n$ 编号。

接下来 $m$ 行，每行三个整数，表示一个操作。

如果操作为 1 a b，表示将节点 $a$ 和节点 $b$ 通过网线连接起来。当 $a = b$ 时，表示连接了一个自环，对网络没有实质影响。

如果操作为 2 p t，表示在节点 $p$ 上发送一条大小为 $t$ 的信息。

输出格式

输出一行，包含 $n$ 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 $1$ 至节点 $n$ 上存储信息的大小。

输入输出样例 #1

输入 #1

输出 #1

13 13 5 3

说明/提示

对于 $30\%$ 的评测用例， $1 \leq n \leq 20$ ， $1 \leq m \leq 100$ 。

对于 $50\%$ 的评测用例， $1 \leq n \leq 100$ ， $1 \leq m \leq 1000$ 。

对于 $70\%$ 的评测用例， $1 \leq n \leq 1000$ ， $1 \leq m \leq 10000$ 。

对于所有评测用例， $1 \leq n \leq 10000$ ， $1 ≤ m ≤ 10^5$ ， $1 \leq t \leq 100$ 。

蓝桥杯 2020 第一轮省赛 A 组 J 题（B 组 J 题）。

并集查找启发性合并

并集查找uf，记录连通关系。re[i]记录连通区域i所有节点，初始re[i]只有一个元素i。cntg[i] 记录连通区域i的信息量，cntn[i]记录节点i的信息量。最终节点i属于连通区域g，则i的信息量是cntg[g]+cntn[i]。
操作一：令两条边分属连通区域g1,g2。如果g1==g2则什么都不干。
g1 $\neq$ g2，uf连通两点,新连通区域是g2，则swap(g1,g2)。如果re[g1].size() <re[g2].size() ，swap(re[g1],re[g2]) swap(cnt1[g1],cnt2[g1])。将g2合并到g1的re过程：
cnt2[i] -= (cnt1[g1]-cnt[j2]), $\in re[g2]$ re[g2]复制到re[g1]
操作二：令p的连通区域是g，则cnt1[g] +=t。
cnt1和cnt2都用int。启发性合并时间复杂度是:O(nlogn)

代码

核心代码

#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<array>

#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();
		while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
		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 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;
};


class Solution {
public:
	vector<int> Ans(const int N, vector<tuple<int, int, int>>& que) {
		CUnionFind uf(N);
		vector<vector<int>> re(N);
		vector<int> cntg(N), cntn(N);
		for (int i = 0; i < N; i++) {
			re[i].emplace_back(i);
		}
		for (auto& [kind, up, vt] : que) {
			up--;
			if (1 == kind) {
				vt--;
				int g1 = uf.GetConnectRegionIndex(up);
				int g2 = uf.GetConnectRegionIndex(vt);
				if (g1 == g2) { continue; }
				uf.Union(up, vt);
				if (g1 != uf.GetConnectRegionIndex(up)) {
					swap(g1, g2);
				}
				if (re[g1].size() < re[g2].size()) {
					swap(re[g1], re[g2]);
					swap(cntg[g1], cntg[g2]);
				}
				for (const auto& i : re[g2]) {
					cntn[i] -= (cntg[g1] - cntg[g2]);
				}
				re[g1].insert(re[g1].end(), re[g2].begin(), re[g2].end());
			}
			else {
				const int g = uf.GetConnectRegionIndex(up);
				cntg[g] += vt;
			}
		}
		vector<int> ans(N);
		for (int i = 0; i < N; i++) {
			ans[i] = cntn[i] + cntg[uf.GetConnectRegionIndex(i)];
		}
		return ans;
	}
};


int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	//ios::sync_with_stdio(0); cin.tie(nullptr);
	CInBuff<> in; COutBuff<10'000'000> ob;	
	int N;
	cin >> N;
	auto ope = in.Read<tuple<int, int, int>>();
#ifdef _DEBUG		
		printf("N=%d", N);
		Out(ope, "ope=");
		//Out(que, "que=");
		//Out(B, "B=");
		//Out(que, "que=");
		//Out(B, "B=");
#endif // DEBUG	
		auto res = Solution().Ans(N,ope);
		for (const auto& i : res)
		{
			cout << i << " ";
		}

	return 0;
}

单元测试

int N;
		vector<tuple<int, int, int>> ope;
		TEST_METHOD(TestMethod11)
		{
			N = 4,ope = { {1,1,2},{2,1,10},{2,3,5},{1,4,1},{2,2,2},{1,1,2},{1,2,4},{2,2,1} };
			auto res = Solution().Ans(N, ope);
			AssertEx({ 13,13,5,3 }, res);
		}

扩展阅读

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