洛谷 P3907 圈的异或

xiaoxiao2021-03-01  16

题目描述

给出无向图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; }
转载请注明原文地址: https://www.6miu.com/read-3100043.html

最新回复(0)