洛谷P3907《圈的异或》

七月 12, 2019 4047

暴力 DFS 即可(???)

题目描述

给出无向图G，边(A_i,B_i) 的权是C_i，判断下列性质是否成立：

对于任意圈C，其边权的异或和是0

输入格式

第1 行，1 个整数T，表示数据的组数。

每组数据第1 行，2 个整数N,M，表示图G 点和边的数量。

M 行，每行3 个整数A_i,B_i,C_i

输出格式

对每个数据输出一行，“Yes” 或者“No”

输入输出样例

输入 #1

1
2
3
4
5
6
7
2
3 3
1 2 1
2 3 2
3 1 3
1 1
1 1 1

输出 #1

1
2
Yes
No

解析

第一反应搜索

其他的都没的说，如何判断异或和？

维护一个 \text{prefix[x]}​ 数组表示 dfs 序中从起点到点 \text{x}​ 的边权异或和，可以理解为一个类似于前缀和的东西
它工作是这样一个过程：

image-20190712204439157

比如说这么一个图，我从 6 开始搜索

image-20190712205341779

当前搜到了 5，检测出来返祖边了，在这停下不知所措
黑色部分是 \text{prefix[5]} ，青色部分是 \text{prefix[1]}

那么答案就是从 1 走到 5 的异或和（设为 X ） \text{xor} \text{weight}(1,5)
X 怎么求？来想一想 \text{xor} 的性质吧： a \text{ xor } a=0, a\text{ xor }0=a
那么……
MATHJAX-SSR-1478
\text{prefix[5]}=X \text{ xor prefix[1]}
所以 \text{prefix[5] xor prefix[1]}
=X \text{ xor prefix[1] xor prefix[1]}\\=X \text{ xor } 0 \\ = X

！！！
那么求 X 就直接把上面那俩 xor 一下就行了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rep(a,s,t,i) for (int a = s; a <= t; a += i)
#define repp(a,s,t,i) for (int a = s; a < t; a += i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

int getint() { int x; scanf("%d", &x); return x; }
long long int getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 50 + 10;

int T, n, m;
struct Graph{
    struct Edge {
        int next, weight;
        
        Edge() { next = weight = 0; }
        Edge(int next, int weight) : next(next), weight(weight) {}
    };

    std::vector<Edge> head[MAXN];

    int prefix[MAXN];
    bool vis[MAXN], exitNeeded;

    Graph() {
        memset(prefix, 0, sizeof prefix);
        memset(vis, 0, sizeof vis);
        exitNeeded = false;
    }
    
    inline void addEdge(int prev, int next, int weight) {
        head[prev].push_back((Edge) { next, weight });
        head[next].push_back((Edge) { prev, weight });
    }
    void DFS(int now, int last, int ans) {
        if (exitNeeded) return;
        vis[now] = true;
        prefix[now] = ans;
        for (int i = 0, siz = (int) head[now].size(); i < siz && !exitNeeded; ++i) {
            int next = head[now][i].next;
            if (!vis[next]) DFS(next, now, ans ^ head[now][i].weight);
            else {
                // 前面的点被搜过了，返祖边！
                if (now != last) {
                    if (head[now][i].weight ^ prefix[now] ^ prefix[next]) {
                        // 对应解析中 X 的求法
                        exitNeeded = true;
                        return;
                    }
                }
            }
        }
    }
};

int main() {
    T = getint();
    countdown (T) {
        Graph G;
        n = getint(); m = getint();
        for (int i = 1; i <= m; ++i) {
            int prev = getint();
            int next = getint();
            int weight = getint();
            G.addEdge(prev, next, weight);
        }
        for (int i = 1; i <= n; ++i) {
            if (!G.vis[i]) G.DFS(i, 0, 0);
            if (G.exitNeeded) break;
        }
        puts(G.exitNeeded ? "No" : "Yes");
    }
    return 0;
}