题解 [美团2018年CodeM大赛-复赛 C] 边的染色

• 边的染色

题目描述

给定一个无向图，边权为 0 / 1。

给定一些边的权，然后要你去把剩下的边权给定了。

要求对于图中每一个环,边权异或和为 0。

求方案数对 998'244'353 取模。

正解

先给出一个构造解的方法：将每一个点随便定一个点权，然后令边权等于两端点权异或和。

这样一定是合法的，因为一个环内每个点恰好出现了（被异或）两次（环内每一个点的度数都为 2）。

发现这样子给定点权的方案可以唯一对应一种给定边权的合法方案。

现在考虑题目中的边有什么用 —— 限制点权。

不考虑 -1 的边，因为 -1 的边对于点权并没有限制。

那么在一个联通块内，选择了一个点，那么联通块内所有的点的选择方案就确定了。

如果一个联通块有解，对答案的贡献就只有 2。

最后答案就是所有联通块答案的乘积。

upd :

但是，要发现这种方法是会算重的。。。（我的锅

一个联通块（包含 -1 边）答案还要除以 2（考虑任意一种赋点权方案，所有点权异或 1 后是同一种边权方案

感性理解下吧

代码

这么简洁的思路都有了还需要代码吗？

/* 一个联通块答案还要除以 2 */
#include <bits/stdc++.h>
#define N 100005

using namespace std;

const int mod = 998244353, inv2 = (mod + 1) >> 1;

int n, m;
int head[N], nex[N << 1], to[N << 1], eVal[N << 1], ecnt;

inline int read() {
    int x = 0; bool neg = false; char ch = getchar();
    while(!isdigit(ch)) (ch == '-') && (neg = true), ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return neg ? -x : x;
}
void addE(int u, int v, int w) {
    to[++ecnt] = v, eVal[ecnt] = w;
    nex[ecnt] = head[u], head[u] = ecnt;
}

int pVal[N], vis[N];
void dfs(int u) {
    vis[u] = true;
    for(int i = head[u], v; i; i = nex[i]) {
        if(eVal[i] == -1) continue;
        v = to[i];
        if(vis[v]) {
            if(pVal[v] != (pVal[u] ^ eVal[i])) { // 强制无解
                puts("0");
                exit(0);
            }
        } else {
            pVal[v] = pVal[u] ^ eVal[i];
            dfs(v);
        }
    }
}
void reDfs(int u) {
    vis[u] = true;
    for(int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if(vis[v]) continue;
        reDfs(v);
    }
}

int main() {
    n = read(), m = read();
    for(int i = 1, u, v, w; i <= m; ++i) {
        u = read(), v = read(), w = read();
        addE(u, v, w), addE(v, u, w);
    }

    int ans = 1;
    for(int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        pVal[i] = 0, dfs(i);
        ans = 2 * ans % mod;
    }

    memset(vis, 0, sizeof vis);
    for(int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        reDfs(i);
        ans = 1LL * inv2 * ans % mod;
    }
    printf("%d\n", ans);
    return 0;
}