[洛谷春令营 D7T2] 圈的异或【DFS】
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; }
发表评论