AGC004 F

74 阅读 0 评论 49 点赞

我是靠谱客的博主糟糕柚子，最近开发中收集的这篇文章主要介绍AGC004 F，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
给出一个无向无自环无重边连通图，n个点，m条边。有黑白两种颜色，初始全白。每次操作选相邻的两个同色点，把他们变成另一种颜色。现在要将所有点变成黑色，问是否有解。如果有，问最少操作次数。
n<=10^5
m=n或m=n-1

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 110000
#define LL long long
using namespace std;
struct node{int y,nex;}a[2*N];
int fir[N],len,n,m,cnt,u,v,o,num,f[N],g[N],c[N],A[N];
LL ans;
void ins(int x,int y)
{
    a[++len].y=y;a[len].nex=fir[x];fir[x]=len;
}
void dfs(int x,int fa)
{
    for(int k=fir[x];k;k=a[k].nex)
    {
        int y=a[k].y;
        if(y==fa) continue;
        if(c[y]==0)
        {
            c[y]=-c[x];
            dfs(y,x);
        }
        else
        {
            u=x;v=y;
            if(c[x]==c[y]) o=1;
            else o=0;
        }
    }
}
void dp(int x,int fa)
{
    f[x]=c[x];
    for(int k=fir[x];k;k=a[k].nex)
    {
        int y=a[k].y;
        if(y==fa || (x==u && y==v) || (x==v && y==u)) continue;
        dp(y,x);
        f[x]+=f[y];
        g[x]+=g[y];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    c[1]=1;
    dfs(1,0);
    if(m==n-1)
    {
        dp(1,0);
        if(f[1]) {printf("-1n");return 0;}
        for(int i=1;i<=n;i++) ans+=abs(f[i]);
        printf("%lldn",ans);
    }
    else if(o==1)
    {
        dp(1,0);
        if(f[1]%2) {printf("-1n");return 0;}
        int t=f[1];
        c[u]-=t/2;c[v]-=t/2;ans=abs(t/2);
        dp(1,0);
        for(int i=1;i<=n;i++) ans+=abs(f[i]);
        printf("%lldn",ans);
    }
    else
    {
        g[u]++;g[v]--;
        dp(1,0);
        if(f[1]) {printf("-1n");return 0;}
        for(int i=1;i<=n;i++)
            if(g[i]==0) ans+=abs(f[i]);
            else if(g[i]==1) A[++num]=-f[i];
            else A[++num]=f[i];
        A[++num]=0;
        sort(A+1,A+num+1);
        int t=A[(num+1)/2];
        for(int i=1;i<=num;i++) ans+=abs(t-A[i]);
        printf("%lldn",ans);
    }
    return 0;
}

题解：
出题人脑洞好大。。

先考虑树的情况，转换一下模型。
由于树是二分图，我们可以给每个点标上0或1。然后发现原操作就变成了交换两个相邻的0和1，目标是让原来为0的地方变成1，原来为1的地方变成0。
为了方便，把1理解为一个硬币，0理解为空位，一次操作就是把硬币移到空位中。目标就是所有硬币和空位位置交换。注意不同硬币的移动是相互独立的。
此时容易发现，当硬币数和空位数相等时才有解，而且是唯一解。
具体来说，把硬币写成1，空位写成-1，si代表i的子树和，答案就是 $sum_{i=1}^nabs(s_i)$

考虑奇环的情况。
现在环上找到一条边(u,v)，将他断开，变成一棵树，转换二分图，树上边的操作依然可以理解为移动硬币。不失一般性，可以让硬币数小于等于空位数。
u和v必定在二分图同一侧，那么这条边只有在两点同色时可操作，操作的结果是反色。就相当于在这两个点加入或删除两个硬币。由于硬币数的奇偶性不改变，所以原图中硬币和空位奇偶性不同就无解。由于硬币较少，我们一定不会删除硬币，然后发现加入硬币数量是一定的，就代表这条边的操作次数是一定的，剩下的就是树上操作，有唯一解。

考虑偶环情况。
此时是二分图，使用移动硬币模型，初始硬币数等于空位数有解。
依然断开环上一条边(u,v)。
令u到v运了x个硬币，x可以取负数，代表v到u运。yy一下发现总代价关于x是单峰的，可以三分。不过有个更巧妙的做法。
直接在u处减少x个硬币，v处增加x个硬币，统计子树和时同时统计x的系数ki
那么答案的形式就是 $abs(x)+sum_{i=1}^nabs(k_ix+s_i)$
ki的取值只会是-1,0,1。将ki=0的直接加入答案，剩下的部分就可以看成数轴上若干点到某点的距离和最小值，找中位数即可。