[bzoj 4025] 二分图

思路

线段树分治

如果不考虑出现和消失的时间,只管加边,应该如何操作?很显然和NOIP2011关押罪犯是类似的,搞一个并查集,如果在$x$和$y$之间连一条边,就合并$x, y’$和$x’, y$

那么考虑出现和消失的时间。我们可以搞一棵线段树,把一条边分成最多$\log{T}$段,像区间加一样挂到所有它存在的时间段内的线段树节点上。然后我们来dfs遍历这棵线段树,如果当前出现冲突的情况,那么当前遍历到的节点所表示的区间内,每一个时间点的答案都是No。如果顺利遍历到了叶子节点而且没有冲突,那么当前节点表示的时间的答案就是Yes

代码

#include <iostream>
#include <cstdio>
#include <vector>

#define mp std::make_pair
#define fi first
#define se second

int N, M, T, top, fa[200010], dep[200010], sf[4000010], sd[4000010];
std::vector<std::pair<int, int> >vec[400010];
std::vector<std::pair<int, int> >::iterator it;

int find(int x) {while(fa[x])x=fa[x];return x;}

void merge(int x, int y){
	x=find(x); y=find(y);
	if(x==y) return;
	if(dep[x]>dep[y]) std::swap(x, y);
	fa[x]=y; sf[++top]=x;
	if(dep[x]==dep[y]) sd[top]=1, dep[y]++;
	else sd[top]=0;
}

void insert(int p, int L, int R, int l, int r, std::pair<int, int>val){
	if(l<=L && R<=r) {vec[p].push_back(val); return;}
	if(2*l<=L+R) insert(p<<1, L, (L+R)/2, l, r, val);
	if(2*r>L+R)  insert(p<<1|1, (L+R)/2+1, R, l, r, val);
}

void divide(int p, int L, int R){
	 int tmp=top;
	for(it=vec[p].begin(); it!=vec[p].end(); it++){
		if(find(it->fi)==find(it->se)){
			for(int i=L; i<=R; i++)
				puts("No");
			for(; top>tmp; top--) dep[fa[sf[top]]]-=sd[top], fa[sf[top]]=0;
			return;
		}
		merge(it->fi, it->se+N);
		merge(it->se, it->fi+N);
	}
	if(L==R) puts("Yes");
	else     {divide(p<<1, L, (L+R)/2); divide(p<<1|1, (L+R)/2+1, R);}
	for(; top>tmp; top--) dep[fa[sf[top]]]-=sd[top], fa[sf[top]]=0;
}

int main(){
	int x, y, s, t;
	scanf("%d%d%d", &N, &M, &T);
	for(int i=1; i<=M; i++){
		scanf("%d%d%d%d", &x, &y, &s, &t);
		if(s==t) continue; 
		insert(1, 1, T, s+1, t, mp(x, y));
	}
	divide(1, 1, T);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注