题目大意

给定一张 n 个点 m 条边的无向连通图,初始时每个点均为白色。每次你可以选择一条两个端点颜色相同的边,并将它们一起变色(白变黑,黑变白)。你需要求出将每个点均变为黑色的最少步数。

数据范围

$$1 \leq n \leq 10^5, n-1 \leq m \leq n$$

题目分析

对于树

由于树是一种二分图,所以我们可以将所有点二分染色,相当于将一些点反色,问题转化为使整棵树所有节点反色的最少步数。

那么我们可以在所有的黑点上放上一枚硬币,然后问题转化为黑点将硬币沿边转移到白点上,使得所有黑点上没有硬币,所有白点上都有一枚的方案数。

按照一般贪心思想,将黑点的点权设为1,白点点权设为-1.然后求子树点权和$f(x)$。假如子树的点权和是正,说明要有一些硬币从子树里转移出去。若为负,则说明要有一些转移进来。转移出去和进来花费都是1,所以答案就是$\sum abs(f(x))$

而无解的情况就是$f(root)!=0$的情况啦。

对于奇环

现在树上多了条边,形成了一个奇环。那么该边两端的点应该是同色的,那么我们可以选择该边若干次,将该边两端的点上的硬币(带权,硬币数量可以是负数,可以理解为对硬币的需求量)同时消失。

那么我们知道,对树跑一遍上面讲的dp后,若$f(x)$不为0,说明有多余的硬币不知道往哪里放,那么就应该通过这两点将硬币消灭。所以对这两个点的点权同时减去$\frac{f(x)}{2}$即可。当然,如果$f(x)$不能被2整除,显然是无解的。

对于偶环

现在树上多了条边,形成了一个偶环。那么该边两端的点应该是异色的,那么我们只是多了一条可以转移硬币的边而已。我们假设通过这条边转移了$x$枚硬币(同样可以是负数)。那么该边一端的点a的硬币数应该减x,另一边的点b应该加上x。

a所在的子树硬币数应该减去x,b所在的子树硬币数应该加上x。那么我们设第二个权值$g(a)=-1$,$g(b)=1$,其他g值为子树里g值和。这样的花,答案就应该是:

$$abs(x)+\sum abs(f_i+g_ix)$$

不知道米娜桑有没有做过这样一道题洛谷P3819 松江1843路,这道题里就提到了对于这种式子的经典贪心方法。首先对于$g_i=0$,直接计算$f_i$的贡献。否则由于$g_i$只有两个取值,-1和1,所以可以看作数轴上有若干个点,每个点的坐标是$f_ig_i$,找一个点,使得该点到其他所有点的距离和最优。由那道题的贪心思想,可以知道x取所有点的中位数最优。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005;
int n,m,T,tot,uu,vv,ww,ans,js;
int h[N],ne[N<<1],to[N<<1];
int a[N],b[N],f[N],g[N],kl[N];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x,int las) {
    for(int i=h[x];i;i=ne[i]) {
        if(to[i]==las) continue;
        if(!a[to[i]]) a[to[i]]=-a[x],dfs(to[i],x);
        else uu=x,vv=to[i],ww=(a[to[i]]==a[x]);
    }
}
void dp(int x,int las) {
    f[x]=a[x],g[x]=b[x];
    for(int i=h[x];i;i=ne[i]) {
        if(to[i]==las||(x==uu&&to[i]==vv)||(x==vv&&to[i]==uu)) continue;
        dp(to[i],x),f[x]+=f[to[i]],g[x]+=g[to[i]];
    }
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int x,y;
    T=read();
    while(T--) {
        n=read(),m=read();
        tot=ans=0;for(int i=1;i<=n;++i) h[i]=0;
        for(int i=1;i<=m;++i) x=read(),y=read(),add(x,y),add(y,x);
        if(n&1) {puts("-1");continue;}
        for(int i=1;i<=n;++i) a[i]=b[i]=0;
        a[1]=1,dfs(1,0);
        if(m==n-1) {//对于树
            dp(1,0);
            if(f[1]) {puts("-1");continue;}//无解
            for(int i=1;i<=n;++i) ans+=abs(f[i]);
            printf("%d\n",ans);continue;
        }
        if(ww) {//对于奇环
            dp(1,0);
            if(f[1]%2) {puts("-1");continue;}
            ans+=abs(f[1]/2),a[uu]-=f[1]/2,a[vv]-=f[1]/2,dp(1,0);
            for(int i=1;i<=n;++i) ans+=abs(f[i]);
            printf("%d\n",ans);
        }
        else {//对于偶环
            b[uu]=1,b[vv]=-1,dp(1,0),js=0;
            if(f[1]) {puts("-1");continue;}
            for(int i=1;i<=n;++i)
                if(!g[i]) ans+=abs(f[i]);
                else kl[++js]=g[i]*f[i];
            kl[++js]=0,sort(kl+1,kl+1+js);//kl[++js]=0:由于答案里还有一个abs(x),所以0也应该加进去
            int zws=kl[(js+1)/2];
            for(int i=1;i<=js;++i) ans+=abs(kl[i]-zws);
            printf("%d\n",ans);
        }
    }
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *