[洛谷春令营 D7T2] 圈的异或【DFS】

• 2018-02-21
• 0
• 0

Problem:

题目描述

给出无向图 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”

输入输出样例

2
3 3
1 2 1
2 3 2
3 1 3
1 1
1 1 1

Yes
No

说明

• 对于50% 的数据，$N,M\le 20$

• 对于100% 的数据，1≤N, M≤50, 1≤A_i​, B_i​≤N, 0≤C_i​<2¹⁶

Solution:

这道题似乎是大水题啊。。

枚举每个点，跑一遍 DFS，暴力找出回到起点的路径的异或和即可。

一定要注意每组数据读入时都要将图清空。

Code: O(TN²) [2058K, 0MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int T, N, M, startPos;
bool vis[100];

struct Edge{
	int np, val;
	Edge *nxt;
};

struct Graph{
	Edge E[200], *V[100];
	int tope;
	
	inline void clear() {tope = 0, memset(V, 0, sizeof(V));}
	
	inline void addedge(int u, int v, int w){
		E[++tope].np = v, E[tope].val = w;
		E[tope].nxt = V[u], V[u] = &E[tope];
	}
} G;

inline bool dfs(int u, int xorv){
	vis[u] = 1;
	for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){
		if(ne->np == startPos){
			if(xorv ^ ne->val) return 0;
			else continue;
		}
		if(vis[ne->np]) continue;
		if(!dfs(ne->np, xorv ^ ne->val)) return 0;
	}
	return 1;
}

int main(){
	getint(T);
	while(T--){
		getint(N), getint(M);
		G.clear();
		for(register int i = 1; i <= M; i++){
			int A, B, C;
			getint(A), getint(B), getint(C);
			G.addedge(A, B, C), G.addedge(B, A, C);
		}
		bool flag = 1;
		for(register int i = 1; i <= N; i++){
			startPos = i, memset(vis, 0, sizeof(vis));
			if(!dfs(i, 0)) {flag = 0; break;}
		}
		if(flag) puts("Yes"); else puts("No");
	}
	return 0;
}