首页 技术 正文
技术 2022年11月23日
0 收藏 330 点赞 3,800 浏览 1628 个字

经典动态二分图问题。

考虑solve(l,r)分治成l,mid和mid+1,r。先将区间[mid+1,r]中的点全部加入图中,若此时存在奇环则ans[l..mid]全部为0,否则递归到左边。

递归完左边后将右边的点全部删去,左边点全部加入,按同样的方法处理右边。

判断奇环使用可撤销带权并查集,注意多组数据不要用memset。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
int T,n,m,top,cnt,u,v;
int fa[N],sz[N],d[N],ans[N],h[N],nxt[N],to[N];
struct P{ int a,b,c; }s[*N];
struct S{ int x,y; };
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void init(){ cnt=; rep(i,,n) fa[i]=i,sz[i]=,d[i]=,h[i]=; } S get(int x){
if (fa[x]==x) return (S){x,};
S t=get(fa[x]); return (S){t.x,t.y^d[x]};
} void uni(int x,int y){
int t1=get(x).y; x=get(x).x;
int t2=get(y).y; y=get(y).x;
if (sz[x]<sz[y]) swap(x,y);
s[++top]=(P){,y,y}; s[++top]=(P){,x,sz[x]}; s[++top]=(P){,y,};
fa[y]=x; d[y]=t1^t2^; sz[x]+=sz[y];
} void cancel(int x){
if (s[x].a==) fa[s[x].b]=s[x].c;
if (s[x].a==) sz[s[x].b]=s[x].c;
if (s[x].a==) d[s[x].b]=s[x].c;
} void solve(int l,int r){
if (l==r) { ans[l]=; return; }
int mid=(l+r)>>,tmp=top; bool flag=;
rep(u,mid+,r)
for (int i=h[u]; i; i=nxt[i]){
int v=to[i];
if (v>=l && v<=mid) continue;
if (get(u).x!=get(v).x) uni(u,v);
else if (get(u).y==get(v).y) { flag=; break; }
}
if (flag) rep(i,l,mid) ans[i]=; else solve(l,mid);
while (top>tmp) cancel(top--); flag=;
rep(u,l,mid)
for (int i=h[u]; i; i=nxt[i]){
int v=to[i];
if (v>mid && v<=r) continue;
if (get(u).x!=get(v).x) uni(u,v);
else if (get(u).y==get(v).y) { flag=; break; }
}
if (flag) rep(i,mid+,r) ans[i]=; else solve(mid+,r);
while (top>tmp) cancel(top--);
} int main(){
freopen("hdu5354.in","r",stdin);
freopen("hdu5354.out","w",stdout);
for (scanf("%d",&T); T--; ){
scanf("%d%d",&n,&m); init();
rep(i,,m) scanf("%d%d",&u,&v),add(u,v),add(v,u);
solve(,n);
rep(i,,n) printf("%d",ans[i]); puts("");
}
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141751.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,508
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,314
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站