首页 > 代码库 > BZOJ 3563 DZY Loves Chinese / BZOJ 3569 DZY Loves Chinese II 随机化+高斯消元解异或方程组
BZOJ 3563 DZY Loves Chinese / BZOJ 3569 DZY Loves Chinese II 随机化+高斯消元解异或方程组
题目大意:给出一个无向图,问删掉k条边的时候,图是否联通。
思路:虽然我把这两个题放在了一起,但是其实这两个题可以用完全不同的两个解法来解决。
第一个题其实是DZY出错了。。。把每次的边数也异或了,那就直接用这个性质一个一个往后推就行了。。最后一个暴力求一下。。
第二个题才是本意啊。
听到做法的时候我惊呆了。。
首先是将整个图中拆出一个树,那么所有边就分为树边和非树边。将所有非树边都加一个随机权值。树边的权值是所有能够覆盖它的非树边的权值的异或和。
把整个图拆开的充要条件是拆掉一条树边,同时将所有覆盖它的非树边也要拆掉,这些边的异或和正好等于0.这个就可以用高斯消元解异或方程组来解决了。
神啊神啊神啊神啊。。。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000010 using namespace std; struct Edge{ int x,y,len; bool tree_edge; void Read() { scanf("%d%d",&x,&y); } }edge[MAX]; int points,edges,asks; int head[MAX],total = 1; int next[MAX],aim[MAX]; bool v[MAX]; int _xor[MAX]; inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void BuildTree(int x,int last) { v[x] = true; for(int i = head[x]; i; i = next[i]) if(!v[aim[i]]) { edge[i >> 1].tree_edge = true; BuildTree(aim[i],x); } } void DFS(int x,int last) { for(int i = head[x]; i; i = next[i]) if(edge[i >> 1].tree_edge && aim[i] != last) { DFS(aim[i],x); edge[i >> 1].len = _xor[aim[i]]; _xor[x] ^= _xor[aim[i]]; } } int temp[MAX]; inline bool GaussElimination(int cnt) { int k = 0,i; for(int j = 1 << 30; j; j >>= 1) { for(i = k + 1; i <= cnt; ++i) if(temp[i]&j) break; if(i == cnt + 1) continue; swap(temp[i],temp[++k]); for(int i = 1; i <= cnt; ++i) if(temp[i]&j && i != k) temp[i] ^= temp[k]; } return temp[cnt]; } int main() { srand(19970815); cin >> points >> edges; for(int i = 1; i <= edges; ++i) { edge[i].Read(); Add(edge[i].x,edge[i].y); Add(edge[i].y,edge[i].x); } BuildTree(1,0); for(int i = 1; i <= edges; ++i) if(!edge[i].tree_edge) { edge[i].len = rand(); _xor[edge[i].x] ^= edge[i].len; _xor[edge[i].y] ^= edge[i].len; } DFS(1,0); cin >> asks; int last_ans = 0; for(int cnt,x,i = 1; i <= asks; ++i) { scanf("%d",&cnt); //cnt ^= last_ans; for(int j = 1; j <= cnt; ++j) { scanf("%d",&x); x ^= last_ans; temp[j] = edge[x].len; } bool flag = !GaussElimination(cnt); if(!flag) { puts("Connected"); ++last_ans; } else puts("Disconnected"); } return 0; }
BZOJ 3563 DZY Loves Chinese / BZOJ 3569 DZY Loves Chinese II 随机化+高斯消元解异或方程组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。