题解 AT2046 【[AGC004F] Namori】

· · 题解

题目链接

AT2046 (AGC004F) Namori (这个是luogu上的链接）

luogu交不上去用这个 (这个是Vjudge上的链接)

一些思路

1.奇偶性判断

当 n 为奇数时绝对无解，直接输出-1即可。

证明：

如果把每一个点每次黑白的变化叫做“一次变化”， 那么当有解是每个点必经过奇数次变化。 当 n 为奇数时，全图所需的总变化数就为奇数。 而一次操作等于两次变化，由奇偶性易得无解。

这小学生都会证我写它干吗

当然，也不是 n 为偶数就一定有解，比如这个：

2.注意数据范围

注意到 n-1 \leq m \leq n，并且图是联通的，可知这张图是一棵树或者一棵基环树。

所以可以轻松看出这是一道基环树题。

3.转换所求内容

原题的操作为“把两个相连的同色的点的颜色转换”。

但是直接搜很难写。毕竟可能还有一对点要变1,000多次的毒瘤数据存在。

所以，需要一些技巧：

以样例为例：

此时每次操作相当于将两个颜色不同的点对调。

而目标状态即黑白点对调。

由此也可看出对于二分图，有解的条件就是染色后黑白点数目相等。

先看树，考虑每颗子树：

若有 a 个黑点和 b 个白点，那么目标情况就是 b 个黑点和 a 个白点。

假设 a > b，那么从子树根往上的那一条边至少要往外输出 |\ a-b\ | 个黑点，所以在这条边上至少要交换 |\ a-b\ | 次。

而交换了 |\ a-b\ | 次以后，这棵子树内的黑子就能通过树内的互相交换达到目标状态，所以这一条边交换 |\ a-b\ | 次是可以取到的。

那么将每一条边都取这个最小值，即得最小答案。

关于具体求解，令黑点为-1权值,白点为1权值，dfs跑一边求子树总权值就可以了。同时，记这个权值为 \{a\}。则 ans=\sum_{i=1}^{n}|a_i|。

再看看偶环。

先剪掉一条边按树处理。

接下来考虑剪掉的这条边的贡献：

向上输送 x 点权值后会变成这样。

而又有 ans=\sum_{i=1}^{n}|a_i|，所以这条边要使环上的数的绝对值总和最小。

在环上，对于这条边右边的点，ans_{part}=\sum|a_i-x|，对于右边的点，ans_{part}=\sum|a_i+x|=\sum|-a_i-x|。

为了处理，维护数组 \{k\}，使 k_i=\sum_{j\in\{son\} }k_j。然后把剪掉的边左右分别标上1和-1，就可以标记左右半环。

所以 ans_{cycle}=\sum_{i \in \{x|k_x!=0\}}{|a_i \times k_i-x|}。

如果把 a_i \times k_i 标记到数轴上，那么就变成了一个求某一点到一堆点的距离和的问题。

由初中知识可得 x 取中位数时 ans_{cycle} 最小，ans 也就最小。

最后注意 ans=ans_{cycle}+ans_{left}+x，不要忘记加 x。

这个操作可以在 \{a_i \times k_i\ |\ k_i!=0\} 取中位数前加入一个0实现。（不会影响中位数在的区间，|0-x|=x）

一样的，先间隔染色。

发现有一条边两端的点同色（因为不是二分图）。

此时操作这条边的效果就是使黑点数量+2（全为白时）或-2（全为黑时）。

所以整张图的 sum_a 值为偶数时即有解（其实这个条件是与n为偶数对等的）。

先预先使用这一条边操作 \frac{sum_a}{2} 次去掉 sum_a，然后就可以不管这一条边了。

于是标记这条边后在dfs时进行特判，剪掉这条边。

发现剪掉以后就变成一棵树，和树一样处理就好（最后记得答案不要忘记加 \frac{sum_a}{2}）。

code:

#include<bits/stdc++.h>
using namespace std;
// #define int long long
void read(int &x)
{
    int r = 0, ne = 1;
    char c;
    while (c < '0' || c > '9')
    {
        if (c == '-')
            ne = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        r = r * 10 + c - '0';
        c = getchar();
    }
    x = r * ne;
}
struct  Edge
{
    /* data */
    int i,nxt;
};
/* 链表 */
int h[100002],tot;
Edge e[200002];
inline void _add(int x,int y){
    e[++tot].i=y;
    e[tot].nxt=h[x];
    h[x]=tot;
    e[++tot].i=x;
    e[tot].nxt=h[y];
    h[y]=tot;
}
/* 输入 */
int n,m,x,y;
/* 偶环-求解 */
int s[100002],top,mid;
/* dfs */
bool odd;/* 奇环 */
int A,B;/* 环两个连接点 */
int w[100002];/* 点绿色权值(1,-1) */ /* 第二遍扫时存的是子树总权值 */
int k[100002];/* 偶环时标记多余边到LCA的点 */
int sum;/* 权值总和 */
long long ans;/* 答案 */
void dfs(int x,int fa){/* 染色 */
    for(int i=h[x];i;i=e[i].nxt){      
        int o=e[i].i;
        if(o==fa)continue;
        if(w[o]){
            if(w[o]==w[x])
                odd=true;
            A=x,B=o;
        }else{
            w[o]=-w[x];
            // sum+=w[o];
            dfs(o,x);
        }
    }
}
void Dfs(int x,int fa){/* 求解 */
    for(int i=h[x];i!=0;i=e[i].nxt){
        int o=e[i].i;
        if(o==fa||(o==A&&x==B)||(o==B&&x==A))continue;/* 排除基环树的干扰 */
        Dfs(o,x);
        w[x]+=w[o];
        k[x]+=k[o];
    }
}
signed main(){
    read(n),read(m);
    for(register int i=0;i<m;++i){
        read(x),read(y);
        _add(x,y);
    }
    if(n%2){
        puts("-1");
        return 0;
    }
    w[1]=1;
    // sum=1;
    dfs(1,0);
    for(int i=1;i<=n;++i)sum+=w[i];    
    if(m+1==n)/* 树 */{
        if(sum){
            puts("-1");
           return 0;
        }
    }else{
        if(odd)/* 奇环 */{
            //if(sum&1){
            //    puts("-1");
            //    return 0;
            //}
            ans+=abs(sum>>1);
            w[A]-=sum>>1,w[B]-=sum>>1;
        }else/* 偶环 */{
            if(sum){
                puts("-1");
                return 0;
            }else 
                k[A]=1,k[B]=-1;
        }
    }
    Dfs(1,0);
    for(register int i=1;i<=n;++i){
        if(k[i])
            s[++top]=k[i]*w[i];
        else
            ans+=abs(w[i]);
    }
    s[++top]=0;//在栈里处理最后需要加的mid(因为偶环那一条被剪掉的边用了mid次，在后面需要用特判加。
    sort(s+1,s+top+1);
    mid=s[(top+1)>>1];
    for(register int i=1;i<=top;++i)
        ans+=abs(s[i]-mid);
    printf("%lld\n",ans);
    return 0;
}