洛谷P3907《圈的异或》

暴力 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 $
那么……

$\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
#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;
}