首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。