自动搬运

查看原文

来自洛谷，原作者为

	dengchengyu 已经没有什么好害怕的了

搬运于2025-08-24 21:17:42，当前版本为作者最后更新于2025-03-04 21:55:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[中山市赛 2024] 参数拟合 题解

首先考虑把每一对 $x,y$ 连边。

对于每一个联通块，可以把所有 $a_i-b_i$ 汇聚到一个点上，然后考虑怎么分配才能使得答案最小。

即对于一个联通块，设：

显然要平均分配才能最小，于是设 $sz$ 为连通块大小，则：

但是这样是不对的，答案可能会偏大。

考虑一个长度为奇数的环，这里以三为例：$(a,b),(b,c),(c,a)$。

则我们可以进行操作：$(a,b,1),(b,c,-1),(c,a,1)$，发现这样以后 $a$ 就加了二。

所以我们就把 $sum$ 移动到奇数环上，这样贡献就是 $sum \bmod 2$。

我们可以把图黑白染色，如果有一条边两边颜色一样则出现了奇数环。

时间复杂度 $O(n+m)$。

代码：

const int N=2e5+5,M=5e5+5;
#define ll long long 
ll a[N],b[N];
int to[M<<1],nx[M<<1],st[N],tot;
void add(int x,int y){
	to[++tot]=y,nx[tot]=st[x],st[x]=tot;
}
int vis[N];
int bz[N];
int flag[N],rt;
ll ans=0,sz;
void dfs(int x){
	vis[x]=1,sz++;
	for(int i=st[x];i;i=nx[i]){
		int v=to[i];
		if(!vis[v]){
			bz[v]=bz[x]^1;
			dfs(v);
			if(a[v]!=0){	
				a[x]-=a[v];
				a[v]=0;
			}
		}
		else if(bz[v]==bz[x]){
			flag[rt]=1;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
		a[i]=a[i]-b[i];
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			sz=0;
			bz[i]=0;
			rt=i;
			dfs(i);
			if(a[i]<0)a[i]=-a[i];
			if(flag[i])ans+=a[i]%2;
			else {
				ll t=a[i]/sz,t2=a[i]%sz;
				ans+=(sz-t2)*t*t+t2*(t+1)*(t+1);
			}
		}
	}
	printf("%lld\n",ans);
}