题目描述
给出无向图G，边 (Ai,Bi)的权是Ci，判断下列性质是否成立：
对于任意圈C，其边权的异或和是0
输入输出格式
输入格式：
第1 行，1 个整数T，表示数据的组数。
每组数据第1 行，2 个整数 N,M，表示图G 点和边的数量。
M 行，每行3 个整数 Ai，Bi，Ci，
输出格式：
对每个数据输出一行，“Yes” 或者“No”
输入输出样例
输入样例#1：
2 3 3 1 2 1 2 3 2 3 1 3 1 1 1 1 1
输出样例#1：
Yes No
说明
• 对于50% 的数据， N,M≤20
• 对于100% 的数据， 1 <= N,M <= 50 , 1 <= Ai,Bi <= N , 0 <= Ci < 2^16
思路解析
一看数据范围，决定暴力。 枚举每个点，然后dfs，如果回到这个点自己，就判断异或和是不是0 没了
code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN =
55;
const int MAXM =
55;
int n,m,T;
struct Edge {
int next;
int to,w;
} l[MAXM<<
1];
int head[MAXN],cnt=
1;
bool vis[MAXN],flag;
bool v[MAXM];
inline void add(
int x,
int y,
int z) {
cnt++;
l[cnt].next = head[x];
l[cnt].to = y;
l[cnt].w = z;
head[x] = cnt;
return;
}
inline void dfs(
int x,
int from,
int sum,
int syqAK) {
if(flag)
return;
if(vis[x]) {
if(sum && x == syqAK) flag =
true;
return;
}
vis[x] =
true;
for(
register int i = head[x];i;i = l[i].next) {
if(l[i].to == from || v[i])
continue;
v[i] = v[i ^
1] =
true;
dfs(l[i].to,x,(sum xor l[i].w),syqAK);
}
}
int main() {
scanf(
"%d",&T);
while(T--) {
scanf(
"%d%d",&n,&m);
int x,y,z;
for(
int i =
1;i <= m;i++) {
scanf(
"%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for(
int i =
1;i <= n;i++) {
dfs(i,
0,
0,i);
memset(vis,
0,
sizeof(vis));
memset(v,
0,
sizeof(v));
}
if(flag)
printf(
"No\n");
else printf(
"Yes\n");
memset(head,
0,
sizeof(head));
flag =
0;
cnt =
0;
}
return 0;
}
