Chlience

【题解】AtCoder Grand Contest 004 F - Namori
Problem给定一棵基环树,一开始所有点都是白色,每次可以选择一对相邻且同色的点反色(黑 $\Leftright...
扫描右侧二维码阅读全文
27
2019/02

【题解】AtCoder Grand Contest 004 F - Namori

Problem

给定一棵基环树,一开始所有点都是白色,每次可以选择一对相邻且同色的点反色(黑 $\Leftrightarrow$ 白),问最少多少步能使得所有点变成黑色,无解输出 $-1$

Thought

先考虑树的情况,如果将树奇偶分层,那么每次反色就相当于是选择相邻的奇数层点和偶数层点

显然这个东西是可以传递的,所以说可以使得任意两个奇数层和偶数层的点同时反色,其花费是两者之间的距离

那么判断其可行性等价于判断树的奇数层和偶数层的点数是否相同

如何求最小花费呢?
对于每条边,当然我们尽量让所有的路径不穿过这条边,也就是说让每一侧的奇点和偶点尽量匹配,不能匹配的部分就必然经过该边,经过的次数即为奇点偶点数量差

那么对于多了一条边形成基环树的情况,可以分奇环和偶环进行处理

显然偶环是可以进行奇偶分层的,那么即可判断是否合法
接下来对于树部分的每一条边,按照之前的方法计算贡献

然后问题就转化为了在环上某些点进一些流量,在环上某个些点出一些流量,每条边每点流量为 $1$ 的费用,求最小费用 费用流啊!

我们枚举任意一条边的流量 $x$ ,那么可以表示出每条边的流量 $x+b_i$,然后最后需要求的就是 $\min\{\sum_{i}|x+b_i|\}$

这个东西怎么求呢?换句话说,这个东西就是求数轴上到点 $-b_i$ 的最小距离和,直接取中位数就好了

对于奇环来说,我们的奇偶分层就会有点问题,不过没关系,我们不管最后那条返祖边进行强行染色,然后计算没有这条边的总贡献

然后考虑这条边的作用:由于这条边连接了两个本来无法相邻的点,那么使得任意两个奇点和任意两个偶点也可以同时消除,那么相当于这条边连接的两个点向左右分别贡献了(奇点个数 $-$ 偶点个数) $/2$ 的流量,该边的花费也为(奇点个数 $-$ 偶点个数) $/2$

和偶环的区别在于:偶环物质守恒,奇环无中生有

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;

struct Edge {
    int t, n;
}e[N << 1];
int head[N], tot;

int n, m;

void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
void init() {
    n = read(); m = read();
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
}
bool vis[N];
int dep[N], fa[N], siz[N];
int S, T;
long long ans;
int dfs(int x, int _f, int d) {
    vis[x] = 1; dep[x] = d; fa[x] = _f;
    int s = d;
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == fa[x]) continue;
        if(!vis[e[i].t]) s += dfs(e[i].t, x, - d);
        else if(!S) {
            S = e[i].t;
            T = x;
        }
    }
    if(x != 1)
        ans += abs(s);
    siz[x] = s;
    return s;
}
int sta[N], top;
int main() {
    init();
    int ret = dfs(1, 0, 1);
    if(abs(ret) & 1) puts("-1");
    else if(ret && !S && !T) puts("-1");
    else if(!ret && !S && !T) printf("%lld\n", ans);
    else {
        if(dep[S] == dep[T]) {//奇环
            int p = T;
            while(p != S) {
                ans -= abs(siz[p]);
                p = fa[p];
            }
            while(p != 1) {
                ans -= abs(siz[p]);
                p = fa[p];
            }
            ans += abs(ret / 2);
            p = T;
            while(p != S) {
                ans += abs(siz[p] - ret / 2);
                p = fa[p];
            }
            while(p != 1) {
                ans += abs(siz[p] - ret);
                p = fa[p];
            }
            printf("%lld\n", ans);
        }
        else {//偶环
            if(ret) puts("-1");
            else {
                int p = T;
                while(p != S) {
                    sta[++ top] = siz[p];
                    ans -= abs(siz[p]);
                    p = fa[p];
                }
                sta[++ top] = 0;
                nth_element(sta + 1, sta + (top + 1) / 2, sta + top + 1);
                int x = sta[(top + 1) / 2];
                
                ans += abs(x);
                p = T;
                while(p != S) {
                    ans += abs(siz[p] - x);
                    p = fa[p];
                }
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}
Last modification:February 27th, 2019 at 09:45 pm

Leave a Comment