BZOJ 3569 DZY Loves Chinese II ——线性基
2024-08-30 13:20:49
【题目分析】
腊鸡题目卡题面。
大概的意思就是给一张无向图,每次删掉其中一些边,问是否联通。
首先想到的是Bitset,可以做到n^2/64。显然过不了。
然而这是lyd在给我们讲线性基的时候的一道题目。↓
首先构建dfs树。
发现图不联通的时候,当且仅当删去了树边和所有覆盖它的非树边。
所以对于每一条非树边随机一个权值,然后每条树边为所有覆盖它的非树边的权值的异或。
每次判断是否线性无关即可。
神题!
【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath> #include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue> using namespace std; #define maxn 100005
#define maxm 1000005
#define mxle 65
#define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define inf (0x3f3f3f3f) void Finout()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
} int Getint()
{
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;
} vector <int> v[maxn];
int h[maxm],fr[maxm],to[maxm],ne[maxm],en=0,f[maxn],tag[maxm];
int w[maxm],b[maxm];
int vis[maxm]; void add(int a,int b)
{
fr[en]=a; to[en]=b; ne[en]=h[a]; h[a]=en++;
fr[en]=b; to[en]=a; ne[en]=h[b]; h[b]=en++;
} void dfs1(int o,int fa)
{
vis[o]=1;
for (int i=h[o];i>=0;i=ne[i])
{
if (!vis[to[i]]) dfs1(to[i],o);
else if (!w[i]&&to[i]!=fa)
{
w[i]=w[i^1]=rand()*711;
b[o]^=w[i]; b[to[i]]^=w[i];
}
}
} int n,m; void dfs2(int o)
{
vis[o]=1;
for (int i=h[o];i>=0;i=ne[i])
{
if (!vis[to[i]])
{
dfs2(to[i]);
w[i]=w[i^1]=b[to[i]];
b[o]^=b[to[i]];
}
}
} struct Base{
int lb[mxle];
bool add(int x)
{
D(i,30,0)
{
if ((x>>i)&1)
{
if (!lb[i]) {lb[i]=x;return false;}
else x^=lb[i];
}
}
return true;
}
void init(int x){memset(lb,0,sizeof lb);add(x);}
}bas; int q,x,y; int main()
{
memset(h,-1,sizeof h);
srand(20000416);
Finout();
n=Getint();m=Getint();
F(i,1,m) add(Getint(),Getint());
dfs1(1,0);
memset(vis,0,sizeof vis);
dfs2(1);
int ans=0,flag=0;
q=Getint();
F(i,1,q)
{
flag=0;
x=Getint(); bas.init(0);
F(i,1,x)
{
y=Getint(); y^=ans;
if (bas.add(w[2*y-1])) flag=1;
}
flag^=1;
if (flag) printf("Connected\n");
else printf("Disconnected\n");
ans+=flag;
}
}
最新文章
- MongoDB 安装
- 系统进程 zygote(二)—— zygote.rc 脚本
- fil_space_t
- 用js实现选项卡切换效果
- mac上SVN项目管理,提示被锁定的解决方法
- bzoj1878
- RPM工具
- php 图片上传预览(转)
- VS2010/MFC对话框:向导对话框的创建及显示
- wuzhicms 数据迁移策略
- 解题报告8VC Venture Cup 2017 - Elimination Round
- Erlang cowboy websocket 服务器
- 【LeetCode】89.Gary Code
- 微信小程序如何套用iconfont
- HttpRunner框架(一)
- DB2 rollforward 命令使用详解
- 原来 php 中的 json_encode() 只支持utf-8.不支持gbk啊
- PAT甲题题解-1069. The Black Hole of Numbers (20)-模拟
- Eclipse SDK Android Studio 下载地址
- 在Win7 Hyper-v虚拟机中挂接真实机的声卡