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

【二分图染色法 BFS】B4188 [中山市赛 2024] 参数拟合|普及+

news 2025/7/18 12:16:50

本文涉及的基础知识点

C++BFS算法
C++图论

B4188 [中山市赛 2024] 参数拟合

题目描述

在《机械设计与制作》课程中，Jimmy 制作了一款机械臂作为期末作业。在测试与改进阶段，immy 通过实验测得了他设计的机械臂的尺寸、硬度、灵活度、最大抓力等 $n$ 个参数 $A_1, A_2\dots A_n$ 。根据理论计算，机械臂的最佳性能参数为 $B_1, B_2\dots B_n$ 。为了提高机械臂的性能，拿到更高的分数，Jimmy 决定调整机械参数。

由于机械臂各个部件间具有关联性，修改某个参数的同时也会影响到另一个参数。具体来说，只有 m 种调整可以进行：给定 $x_i, y_i)$ ，让 $A_{x_i} \gets A_{x_i} + p, A_{y_i} \gets A_{y_i} + p$ ，其中 $p$ 为任意整数，且调整次数不限。Jimmy 希望通过调整使得 $=\sum \limits_{i=1}^n(A_i - B_i)^2$ 最小，请你帮他算出调整后 $S$ 的最小值。

输入格式

第一行两个整数 $n, m$ ，分别表示机械臂参数的个数，以及调整操作的种类数。

第二行 $n$ 个整数 $A_i$ ，表示机械臂当前的参数值。

第三行 $n$ 个整数 $B_i$ ，表示机械臂理论最佳的参数值。

接下来 $m$ 行每行两个整数 $x_i, y_i$ ，表示每种调整操作的两个目标参数。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

6 3
14 9 1 0 4 7
11 11 5 8 7 3
1 2
3 4
5 6

输出 #1

说明/提示

数据范围

对于 $20\%$ 的数据， $\leq n, m \leq 5$ ， $\leq A_i, B_i \leq 5$ 。
另有 $40\%$ 的数据，所有 $B_i = 0$ 且所有 $x_i = 1$ 。
对于 $100\%$ 的数据， $\leq n \leq 2 \times 10^5$ ， $\leq m \leq 5 \times 10^5$ ， $\leq A_i, B_i \leq 10^5$ 。

注意： $x_i, y_i)$ 可能出现重复。

B4188 [中山市赛 2024] 参数拟合

${x_i,y_i}$ 看做边，令所有边组成的无向图G。
性质一：如果u和v的某条路径经过m条边，如果m是奇数，那么可以u,v都+1(-1)，其它不变;如果m是偶数，那么可以u+1(-1),v-1(+1)，其它不变。
下面用数学归纳法证明：m==1，根据题意符合。
令u经过m条边到x,x经过1条边到达v。如果m是奇数，u,x都+1，x,u都-1，即u+1,v-1。如果m是偶数，u+1,x-1,x+1,v+1，两者都+1。
性质二：如果某个联通区域只有一个点，则A[cur]无法改变。
性质三:如果u、v存在奇数长度的路径，同时存在偶数长度的路径。则u+1,v-1；v+1,v+1。即u+2(-2)，v不变。
性质四：u、v存在奇数长度的路径 $\iff$ 存在奇数长度的环x。u顺时针到v的边 + v顺时针到u经过的边=m，
两个偶数数（奇数）的和是偶数，不是奇数。
性质五：如果某个连通区域存在奇数环。则任意两点u、v都同时存在奇数路径。
两条路径 $u\rightarrow x \rightarrow v$ ， $u\rightarrow x \rightarrow 转一圈到x \rightarrow v$ ,后者比前者刚好多经过一个环。
有奇数环的区域：如果A[i]和B[i]奇偶性相同，则+2,-2直到相等；如果奇偶性不同，+2,-2到 $A [i] + 1 == B [i]$ 。
任意两个奇偶性不同的下标，同时-1，就变成0了。
结论一：存在奇数环的连通区域， $y=\sum(A[i]和B[i]奇偶性不同)$ , y%2个1，其它全部是0。
如果不存在奇数环，二分图。
思路一：同一个点集的经过偶数边，就u++,v–。不同点集，u++,v++。通过u++,v++让所有 $A[i]\ge B[i]$
sum1是x点集A[i]的和,sum2是y点集A[i]的和。x点集和y点集B[i]之和分别为sum3和sum4。
u++,v–，sum1和sum2不变。u++,v++,sum1和sum2同时++。
不失一般性，令z = (sum2-sum)-(sum4-sum3)>0。 d=z/点数c,c1=z%c。
|A[i]-B[i]|的绝对值，有c1和d+1，其它d。x点集的i，A[i] < B[i];y点集的，A[i]>B[i]。
z < 0，取abs(z)，逻辑发生变化，结果不变。
思路二：
同时操作A[i]和A[0]直到A[i]等于B[i]。
最后将A[i]-B[i]均摊到本连通区域所有的点。
注意：但个节点也符合二分图。
时间复杂度: $O (n)$

思路

group[i] ，0,表示i节点分到X组;1,表示i节点分到Y组;-1,表示i节点没有分配。
枚举i，如果group[i]是-1，则BFS。能否二分，如果能二分，v1,v2分别记录X点集和Y点集；如果不能二分，v1和v2不重复记录所有点集。

代码

核心代码

#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 T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(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 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 Solution {
public:long long Ans(vector<int>& A, vector<int>& B, vector<pair<int, int>>& edge) {const int N = A.size(), M = edge.size();auto neiBo = CNeiBo::Two(N, edge, false, 1);vector<int> group(N, -1);function<void(int)> BFS = [&](int node) {if (-1 != group[node]) { return; }bool can = true;vector<int> v[2];queue<int>que;auto Add = [&](int cur, int iG) {if (-1 != group[cur]) {if (iG != group[cur]) { can = false; }return;}group[cur] = iG;v[iG].emplace_back(cur);que.emplace(cur);};Add(node, 0);while (que.size()) {const auto cur = que.front(); que.pop();for (const auto& next : neiBo[cur]) {Add(next, group[cur] ^ 1);}}if (can) {long long ans = 0;for (const auto& i : v[0]) {ans -= B[i] - A[i];}for (const auto& i : v[1]) {ans += B[i] - A[i];}ans = abs(ans);const int size = v[0].size() + v[1].size();const long long c1 = ans / size;const long long c2 = ans % size;m_ans += (c1 + 1) * (c1 + 1) * c2 + c1 * c1 * (size - c2);}else {long long ans = 0;for (const auto& i : v[0]) {ans += (0 != (A[i] - B[i]) % 2);}for (const auto& i : v[1]) {ans += (0 != (A[i] - B[i]) % 2);}m_ans += ans % 2;}};for (int i = 0; i < N; i++) {BFS(i);}return m_ans;}long long m_ans = 0;
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;	int N, M;cin >> N >> M;auto A = Read<int>(N);auto B = Read<int>(N);auto edge = Read<pair<int, int>>(M);
#ifdef _DEBUG	//printf("iH=%d,iA=%d,H=%d,dA=%d",iH,iA,H,dA);Out(A, ",A=");Out(B, ",B=");Out(edge, ",edge=");		/*Out(que, ",que=");*///Out(ab, ",ab=");//Out(par, "par=");//Out(que, "que=");//Out(B, "B=");
#endif // DEBUG	auto res = Solution().Ans(A,B,edge);cout << res << "\n";return 0;
};

单元测试

vector<int> A, B;vector<pair<int, int>> edge;TEST_METHOD(TestMethod11){A = { 14,9,1,0,4,7 }, B = { 11,11,5,8,7,3 }, edge = { {1,2},{3,4},{5,6} };auto res = Solution().Ans(A, B, edge);AssertEx(46LL, res);}

# 扩展阅读

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