首页 > 代码库 > 【bzoj3569】 DZY Loves Chinese II

【bzoj3569】 DZY Loves Chinese II

http://www.lydsy.com/JudgeOnline/problem.php?id=3569 (题目链接)

题意

  给出一个无向图,$Q$组询问,每次询问将原图断掉$C$条边后是否还连通。在线版。

Solution

  神思路。

  我们找到这个图的任意一棵生成树,然后对于每条非树边将其的权值赋为一个随机数。

  对于每条树边,我们将这条树边的权值设为所有覆盖这条树边的边权的异或和。

  那么图不连通当且仅当删除一条树边和覆盖这条树边的所有边集,而由于刚才的处理一条树边和覆盖这条边的所有边集的异或和为零。

  于是问题转化成了对于给定的k条边是否存在一个边权的异或和为零的子集,果断高斯消元,由于使用了随机化所以碰撞率极低。

  ——PoPoQQQ

  好像就是tmp大爷上次说的方法,长见识了。

细节

  种子设大一点?(这不废话)

代码

// bzoj3569#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=500010;int fa[maxn],fe[maxn],head[maxn],c[maxn],cnt,n,m,Q;struct data {int u,v,w,tp;}d[maxn];struct edge {int to,next,w;}e[maxn];int find(int x) {	return fa[x]==x ? x : fa[x]=find(fa[x]);}void link(int u,int v,int w) {	e[++cnt]=(edge){v,head[u],w};head[u]=cnt;	e[++cnt]=(edge){u,head[v],w};head[v]=cnt;}void dfs(int x,int fa) {	for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) {			fe[e[i].to]=e[i].w;			dfs(e[i].to,x);		}}int Dfs(int x,int fa) {	int tmp=0;	for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) {			d[e[i].w].w^=Dfs(e[i].to,x);			tmp^=d[e[i].w].w;		}	return tmp;}int Gauss(int p) {	for (int now=0,i=1<<30;i;i>>=1) {		int k=now+1;		while (!(c[k]&i) && k<=p) k++;		if (k==p+1) continue;		swap(c[++now],c[k]);		for (int j=1;j<=p;j++) if (j!=now && c[j]&i) c[j]^=c[now];	}	return c[p] ? 1 : 0;}int main() {	srand(987532631);	scanf("%d%d",&n,&m);	for (int i=1;i<=n;i++) fa[i]=i;	for (int i=1;i<=m;i++) {		scanf("%d%d",&d[i].u,&d[i].v);		if (find(d[i].u)!=find(d[i].v)) {			fa[find(d[i].u)]=find(d[i].v),d[i].tp=1;			link(d[i].u,d[i].v,i);		}	}	dfs(1,0);	for (int i=1;i<=m;i++) if (!d[i].tp) {			d[i].w=rand();			d[fe[d[i].u]].w^=d[i].w;			d[fe[d[i].v]].w^=d[i].w;		}	Dfs(1,0);	scanf("%d",&Q);	for (int ans=0,i=1,k;i<=Q;i++) {		scanf("%d",&k);		for (int j=1;j<=k;j++) scanf("%d",&c[j]),c[j]^=ans;		for (int j=1;j<=k;j++) c[j]=d[c[j]].w;		int pd=Gauss(k);		ans+=pd;		puts(pd ? "Connected" : "Disconnected");	}	return 0;}

 

【bzoj3569】 DZY Loves Chinese II