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

  • 2018-02-21
  • 0
  • 0

Problem:

题目描述

给出无向图 G,边  的权是 ,判断下列性质是否成立:

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

输入输出格式

输入格式:

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

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

M 行,每行 3 个整数 

输出格式:

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

输入输出样例

输入样例#1:

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

输出样例#1:

Yes
No

说明

• 对于50% 的数据,

• 对于100% 的数据,

Solution:

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

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

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

Code: O(TN2) [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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai