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

【并集查找二分图】P6185 [NOI Online #1 提高组] 序列|省选-

news 2025/7/21 12:52:32

本文涉及知识点

C++并集查找
二分图

P6185 [NOI Online #1 提高组] 序列

题目背景

由于本题数据较难构造，所以无法保证卡掉所有错误做法。

题目描述

小 D 有一个长度为 $n$ 的整数序列 $a1…na_{1 \dots n}$ ，她想通过若干次操作把它变成序列 $b_i$ 。

小 D 有 $m$ 种可选的操作，第 $i$ 种操作可使用三元组 $t_i,u_i,v_i)$ 描述：若 $t_i=1$ ，则她可以使 $a_{u_i}$ 与 $a_{v_i}$ 都加一或都减一；若 $t_i=2$ ，则她可以使 $a_{u_i}$ 减一、 $a_{v_i}$ 加一，或是 $a_{u_i}$ 加一、 $a_{v_i}$ 减一，因此当 $u_i=v_i$ 时，这种操作相当于没有操作。

小 D 可以以任意顺序执行操作，且每种操作都可进行无限次。现在给定序列与所有操作，请你帮她判断是否存在一种方案能将 $a_i$ 变为 $b_i$ 。题目保证两个序列长度都为 $n$ 。若方案存在请输出 YES，否则输出 NO。

输入格式

本题输入文件包含多组数据。

第一行一个正整数 $T$ 表示数据组数。对于每组数据：

第一行两个整数 $n, m$ ，表示序列长度与操作种数。

第二行 $n$ 个整数表示序列 $a_i$ 。

第三行 $n$ 个整数表示序列 $b_i$ 。

接下来 $m$ 行每行三个整数 $t_i,u_i,v_i$ ，第 $i$ 行描述操作 $i$ 。

注意：同一个三元组 $t_i,u_i,v_i)$ 可能在输入中出现多次。

输出格式

对于每组数据输出一行一个字符串 YES 或 NO 表示答案。

输入输出样例 #1

输入 #1

输出 #1

YES
YES
YES

说明/提示

样例 1 解释

第一组数据：使用一次操作 $1$ 。
第二组数据：使用三次操作 $1$ 。
第三组数据：使用三次操作 $1$ ，令 $a_1,a_2$ 都增加 $3$ ，再使用一次操作 $2$ ，令 $a_1,a_3$ 都增加 $1$ 。

数据范围与提示

对于测试点 $\sim 5$ ： $n = 2$ ， $m = 1$ ， $ai,bi≤99a_i,b_i \le 99$ ， $u1≠v1u_1 \ne v_1$ ， $t_1=1$ 。
对于测试点 $\sim 10$ ： $n = 2$ ， $m = 1$ ， $ai,bi≤99a_i,b_i \le 99$ ， $u1≠v1u_1 \ne v_1$ ， $t_1=2$ 。
对于测试点 $\sim 12$ ： $n = 2$ ， $ai,bi≤99a_i,b_i \le 99$ ， $ui≠viu_i \ne v_i$ 。
对于测试点 $\sim 16$ ： $t_i=2$ 。
对于测试点 $17$ ： $\le 20$ 。
对于测试点 $18$ ： $\le 10^3$ 。
对于所有测试点： $\le T \le 10$ ， $\le n,m \le 10^5$ ， $\le a_i,b_i \le 10^9$ ， $ti∈{1,2}t_i \in \{1,2\}$ ， $1≤ui,vi≤n1\le u_i,v_i \le n$ 。

并集查找二分图

如果x、y能进行操作二,y、z也能进行操作二，则(x,z)也进行操作二。如：x++,y–,y++,z–的效果是x++,z–。
性质一：如果(x,y)能进行操作二，则连边，任意连通区域的任意两点都可以进行操作二。
故对同一个连通区域的进行缩点，点权为整个连通区域的和。
如果x,y能进行操作一，y,z能进行操作一。则 x++,y++;y–,z–。则x、z能进行操作二。
性质二：缩点后，对任意能进行操作一的点x,y连通，形成无向图G。如果任意两点通过两条边能够连通，则可以进行操作二。
可以用数论归纳法证明：
任意两点存在偶数边的路径，则可以执行操作二。
任意两点存在奇数边的路径，则可以执行操作一。
性质三：如果G的某个连通区域没有奇数环(二分图)，则此连通区域二分后。起点u，终点v的路径经过n条边。如果n是奇数，则u和v来自不同的点集；如果是偶数，则来自相同的点集(都是左点集或都是右点集)。可以用数学归纳法证明:
f(n)表示经过n条边的路径，起点和终点是否来自于同一点集。
f(1) = 0。f(n+1)=f(n)^1。 $\cdots v \rightarrow w$ ，v,w来自不同点集，故：如果u、v相同的点集，则u、w不同的点集；如果u、v不同的点集，则u、w相同的点集。
小结一：左（右)点集在保证和不变的情况下，可以任意调整。令左点集需要增加num1，右点集需要增加num2，如果 $\neq num2$ 无解，否则有解。
性质四：如果G的某个连通区域有奇数环。则任意两点u、v都有经过偶数边的路径，也有经过偶数的边。令w是奇数环上任意一点。
$\rightarrow w \rightarrow v$ 如果经过奇数条边，则 $\rightarrow w转一圈 \rightarrow v$ 。即此连通区域和不变的情况下任意调整。也可以让和 $±2\pm 2$ 。即此连通区域a、b和的差为偶数。

实现

点i的点权 $w [i] = b [i] - a [i]$ 。
利用uf连通类型2的边。
edge记录类型1的边。
利用uf对edge进行缩点，形成临接边neiBo，被锁掉的点vis[点]=1。vis[点]：0，左点集；1，右点集；-1，未访问。
无论是本来有的自环，还是缩点后产生的自环，都保留。

利用染色法对各连通区域二分，rw1记录左点集的点权之和，nw2记录右点集的点权之和。如果不能二分，n $\iff 是否有解$ 。如果能二分， $\iff 是否有解$

代码

核心代码

#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 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){m_vNodeToRegion[iConnectNO1] = iConnectNO2;}else{m_vNodeToRegion[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:vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;
};class Solution {
public:bool Ans(vector<int>& A, vector<int>& B, vector<tuple<int, int, int>>& ope) {const int N = A.size();vector<int> W(N);for (int i = 0; i < N; i++) {W[i] = B[i] - A[i];}vector<pair<int, int>> edge;CUnionFind uf(N);for (auto [kind, u, v] : ope) {u--, v--;if (2 == kind) {uf.Union(u, v);}else {edge.emplace_back(u, v);}}vector<vector<int>> neiBo(N);for (auto& [u, v] : edge) {const int g1 = uf.GetConnectRegionIndex(u);const int g2 = uf.GetConnectRegionIndex(v);neiBo[g1].emplace_back(g2);neiBo[g2].emplace_back(g1);}auto m = uf.GetNodeOfRegion();vector<int> color(N, -1);for (const auto& [g, v] : m) {for (const auto& i : v) {if (i == g) { continue; }W[g] += W[i];color[i] = 0;}}auto BFS = [&](int root) {if (-1 != color[root]) { return true; }int ws[2] = { 0 };bool bCan = true;queue<int> que;auto Add = [&](int cur, int iColor) {if (-1 != color[cur]) {if (iColor != color[cur]) { bCan = false; }return;}color[cur] = iColor;que.emplace(cur);ws[iColor] += W[cur];};Add(root, 1);while (que.size()) {const auto cur = que.front(); que.pop();for (const auto& next : neiBo[cur]) {Add(next, color[cur] ^ 1);}}if (bCan) {return ws[0] == ws[1];}return (ws[0] + ws[1]) % 2 == 0;};bool ans = true;for (int i = 0; i < N; i++) {ans &= BFS(i);}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	int T,N,M;cin >> T;while (T--){cin >> N >> M;auto A = Read<int>(N);auto B = Read<int>(N);auto ope = Read<tuple<int, int, int>>(M);
#ifdef _DEBUG//printf("N=%d,M=%d", N,M);Out(A, ",A=");Out(B, ",B=");//Out(edge, ",edge=");Out(ope, ",ope=");
#endif // DEBUGauto res = Solution().Ans(A,B, ope);		cout << (res ? "YES" : "NO") << "\n";}return 0;
}

总结

性质一：操作二两次,x++,y–,y++,z–。等效操作二一次。
性质二：操作一两次,x++,y++,y–z–。等效操作二一次。
性质三：先操作一，再操作二，x++,y++,y–,z++。等效操作一。
性质四：操作二，再操作一，x++,y–,y++,z++。等效操作一。
令操作一的边权为-1，操作二的边权为1,整个路径的边权为所有边权相乘。
性质五;如果路径uv的边权是1，则可以对uv进行操作一；否则，可以对uv进行操作二。
根据性质一到性质四边数小于2的路径符合。我们假定边数m的路径符合，则边数m+1的路径符合。
如果前m条边的边权和最有一条边的权相等，根据性质一二符合。
否则，根据性质三四符合。
性质六：任意路径边权为-1的数论为偶数，则边权为1；为奇数，则边权为-1。即边权为1的边可以缩点。

扩展阅读

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