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

dengchengyu · 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);
}