首页 > 代码库 > 【bzoj3237】 Ahoi2013—连通图
【bzoj3237】 Ahoi2013—连通图
http://www.lydsy.com/JudgeOnline/problem.php?id=3237 (题目链接)
题意
给出一个无向图,$Q$组询问,每次询问将原图断掉$C$条边后是否还连通。
Solution
CDQ图分治,并查集维护。实在写不动题了,我能说我是蒯的吗T_T:http://blog.csdn.net/creationaugust/article/details/50889351
细节
bzoj的G++版本是多久以前的了,莫名CE。。
代码
// bzoj3237#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=200010,maxm=5000010;int ans[maxn],del[maxn],fa[maxn],st[maxm];int n,m,Q,tim,top;struct data {int c,id,e[4];}q[maxn];struct edge {int u,v;}e[maxn];namespace Unionset { int find(int x) { if (fa[x]==x) return x; st[++top]=x;st[++top]=fa[x];return fa[x]=find(fa[x]); } void Union(int u,int v) { if (find(u)!=find(v)) { st[++top]=fa[v]; st[++top]=fa[fa[v]]; fa[fa[v]]=fa[u]; } }}using namespace Unionset;void solve(int l,int r) { int now=top,mid=(l+r)>>1,flag=1; if (l==r) { for (int i=0;i<q[l].c && flag;i++) if (find(e[q[l].e[i]].u)!=find(e[q[l].e[i]].v)) flag=0; ans[q[l].id]=flag; for (;now!=top;top-=2) fa[st[top-1]]=st[top]; return; } tim++; for (int i=l;i<=mid;i++) for (int j=0;j<q[i].c;j++) del[q[i].e[j]]=tim; for (int i=mid+1;i<=r;i++) for (int j=0;j<q[i].c;j++) if (del[q[i].e[j]]!=tim) Union(e[q[i].e[j]].u,e[q[i].e[j]].v); solve(l,mid);tim++; for (;now!=top;top-=2) fa[st[top-1]]=st[top]; for (int i=mid+1;i<=r;i++) for (int j=0;j<q[i].c;j++) del[q[i].e[j]]=tim; for (int i=l;i<=mid;i++) for (int j=0;j<q[i].c;j++) if (del[q[i].e[j]]!=tim) Union(e[q[i].e[j]].u,e[q[i].e[j]].v); solve(mid+1,r); for (;now!=top;top-=2) fa[st[top-1]]=st[top];}int main() { 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",&e[i].u,&e[i].v); scanf("%d",&Q);tim=1; for (int i=1;i<=Q;i++) { scanf("%d",&q[i].c);q[i].id=i; for (int j=0;j<q[i].c;j++) scanf("%d",&q[i].e[j]),del[q[i].e[j]]=tim; } for (int i=1;i<=m;i++) if (del[i]!=tim) Union(e[i].u,e[i].v); solve(1,Q); for (int i=1;i<=Q;i++) puts(ans[i] ? "Connected" : "Disconnected"); return 0;}
【bzoj3237】 Ahoi2013—连通图
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。