题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3569
题意：无向图，删边后判断连通性（删后复原），强制在线。
3563 那题强制在线是假的，能推出来答案那种...
考虑怎么做靠谱点：
首先可以有一个思路是任求一棵生成树，边权均为 1，非树边就链上边权加一，每次减掉给出的边后看看有没有边的边权被减到零，可以用链剖或者 lct 什么的做。
发现其实没法做，复杂度会炸。
于是构造一下，每条非树边随机给定一个权值，树边权值为覆盖它的非树边的异或和。
那么不联通的条件当且仅当至少有一条树边满足它被切断且覆盖它的非树边均被切断，即切断的边中有一个子集的异或和为零。
即线性无关，线性基判即可。这份代码交 3563 的话需要将 k 也 xor 一下 ans
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define M 1000010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to; }edge[M]; int val[M]; int head[N],cnt=2; void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } int n,m,q,ans; namespace bas { int p[32]; void clear() {memset(p,0,sizeof(p));} bool ins(int x) { for(int i=31;i>=0;i--) if((x>>i)&1) { if(!p[i]) { p[i]=x; return 1; } x^=p[i]; } return 0; } } bool vis[N]; int a[N]; void dfs1(int x,int fa) { vis[x]=1; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(!vis[to])dfs1(to,x); else if(!val[i]&&to!=fa) { val[i]=val[i^1]=rand(); a[x]^=val[i],a[to]^=val[i]; } } } void dfs2(int x) { vis[x]=1; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(!vis[to]) { dfs2(to); val[i]=val[i^1]=a[to]; a[x]^=a[to]; } } } int main() { srand(19260817); n=read(),m=read(); while(m--) { int x=read(),y=read(); add(x,y),add(y,x); } dfs1(1,0); memset(vis,0,sizeof(vis));; dfs2(1); q=read(); while(q--) { bas::clear(); int k=read(); bool line=1; for(int i=1;i<=k;i++) { int x=read()^ans; if(!bas::ins(val[2*x+1]))line=0; } puts(line?"Connected":"Disconnected"); ans+=line; } return 0; } |
Comments | NOTHING