抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

BZOJ 4025 二分图

发布于：2019年9月8日

传送门

本题暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
	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<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	} 
	return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
	G[u].push_back(v);
}
int col[MAXN],vis[MAXN];
inline void Init(){
	memset(col,0,sizeof(col)),memset(vis,0,sizeof(vis));
	for (register int i=0;i<MAXN;++i) G[i].clear();
}
vector<int>E[MAXN];
int U[MAXN],V[MAXN];
inline bool Check(int u){
	vis[u]=true;
	for (register int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if (vis[v]&&col[v]!=(!col[u])) return false;
		else if (!vis[v]){
			col[v]=!col[u];
			Check(v);
		} 
	}
	return true;
}
inline void AddE(int j){
	for (register int i=0;i<E[j].size();++i){
		int id=E[j][i];
		AddEdge(U[id],V[id]);
		AddEdge(V[id],U[id]);
	}
}
int main(){
	int n=read(),m=read(),T=read();
	for (register int i=1;i<=m;++i) {
		U[i]=read(),V[i]=read();
		int s=read(),e=read();
		for (register int j=s;j<e;++j) E[j].push_back(i);
	}
	for (register int i=0;i<T;++i){
		Init();
		AddE(i);
		bool flag=true;
		for (register int j=1;j<=n;++j){
			if (!vis[j]){
				if (!Check(j)) {
					flag=false;
					break;
				}
			}
		}
		puts(flag?"Yes":"No");
	}
	return 0;
}

注意到暴力的时候，我们从tt转移到t+1t+1的时候，可能只会加入少量的边，如果每次O(n)O(n)计算，会造成大量重复计算。

注意到这张图是二分图等价于这张图里面没有奇环，于是可以并查集维护，维护每个点到它的父亲节点的距离，注意要支持可撤销，所以需要启发式合并。

不妨换一个思路，对于一个时刻tt，只有t∈[s,e]t \in [s,e]，[s,e][s,e]区间里面的加边操作才能对答案产生影响，这个结论可以推广，对于时间在[l,r][l,r]的答案（不妨在这段答案全部都是Yes\rm Yes或者No\rm No），只有[l,r]∈[s,e][l,r] \in [s,e]，[s,e][s,e]区间里面的操作才会对答案产生影响，于是我们想要查询[l,r][l,r]的答案时，先要把[l,r]∈[s,e][l,r] \in [s,e]的操作全部做完，如果操作做完之后，产生奇环，那么就把这段区间的答案全部设成No\rm No，并且撤销并查集。

这样说得有点玄学，为甚假定答案都是一样的呢，看不懂没有关系，请继续往下：

考虑一个类似于线段树的分治结构，Solve(l,r,E)Solve(l,r,E)表示总的边集为EE，求解[l,r][l,r]区间的答案，如果按照上面所说地加边，出现奇环，那么将[l,r][l,r]的答案设成No\rm No，撤销并查集，退出递归，因为之后不管怎么加边，都不可能将这个图变回二分图，如果没有出现奇环，找出来所有s≤mids \le mid的边，加入左边的集合LL，e>mide > mid的边加入右边的集合RR，递归求解Solve(l,mid,L),Solve(mid+1,r,R)Solve(l,mid,L),Solve(mid+1,r,R)。

看到这里你应该明白了，其实这个递归过程是把答案序列按照线段树建树的模式分成许多段，每段答案都是No\rm No，

如图所示，标成红色代表这段答案都是No\rm No，停止递归，标成灰色代表这段根本递归不到，标成绿色代表确定了答案是Yes\rm Yes（绿色只在叶子节点有），标成蓝色代表不知道这段答案是Yes\rm Yes还是No\rm No。

这样为什么是正确的呢，因为对于所有s≤l,e≥rs\le l,e \geq r，都被算在并查集里面，递归求解Solve(l,mid,L)Solve(l,mid,L)的时候，发现只要考虑s≤l,e∈[mid+1,r)s \le l,e \in [mid+1,r)的边，（其他的情况就是s≤l,e≥rs \le l ,e \geq r，在上面的递归里面算到了），刚好是我们加进LL的边，但是注意到我们加进LL的不是e>mide > mid的边，为什么呢，发现我们还要照顾到s≤mids \le mid的边，虽然这些边不一定在下一次递归会加入并查集，但是在更深层的递归就可能，不能把他们漏掉。

时间复杂度分析：注意到每条边至多算一次，于是时间复杂度O(nlog⁡2n)O(n \log ^2 n)（启发式合并还有一个$\log $）

这样使用线段树，巧妙地减少了加边的次数。

接下来考虑并查集如何实现

注意到我们要使∀w∈subtree(fa(u))\forall w \in subtree(fa(u))，v−>fa(v)−>fa(u)−>wv -> fa(v) -> fa(u) -> w和v−>u−>wv -> u -> w长度在mod  2\mod 2意义上面是相等的。

于是dep(v)+val[fa(v)]+dep(w)≡1+dep(u)+dep(w)−dep(LCA(u,w))×2(mod2)dep(v)+val[fa(v)]+dep(w)\equiv 1+dep(u)+dep(w)-dep(LCA(u,w)) \times 2 \pmod{2}

化一下：val[fa(v)]≡dep(u)−dep(v)+1(mod2)val[fa(v)]\equiv dep(u)-dep(v)+1 \pmod{2}

这个式子等价于val[fa(v)]≡dep(u)+dep(v)+1(mod2)val[fa(v)]\equiv dep(u)+dep(v)+1 \pmod{2}

注意到我们还有一个条件要满足：

∀w∈subtree(fa(v))\forall w \in subtree(fa(v))，u−>fa(u)−>fa(v)−>wu -> fa(u) -> fa(v) -> w和u−>v−>wu -> v -> w长度在mod  2\mod{2}意义上面相等，把上面的式子带入，发现也是成立的，于是发现我们的式子很好地把两个条件都满足了

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
    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<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
    #define P pair<int,int>
    #define mp make_pair
    int fa[MAXN],sz[MAXN],val[MAXN];
    inline void Init(int n){
        for (register int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
    }
    int GetDep(int i){
        return fa[i]==i?val[i]:GetDep(fa[i])+val[i];
    }
    int Find(int i){
        return fa[i]==i?i:Find(fa[i]);
    }
    inline bool Merge(int u,int v,stack<P> &s){//形成奇环return false，else return true
        int tu=u,tv=v;
        u=Find(u),v=Find(v);
        if (u==v){
            return !((GetDep(tu)+GetDep(tv))%2==0);
        }
        if (sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v],fa[v]=u;
        val[v]=GetDep(tu)+GetDep(tv)+1;
        s.push(mp(u,v));
        return true;
    }
    inline void Reverse(stack<P> &s){//回溯
        while (s.size()){
            int u=s.top().first,v=s.top().second;
            fa[v]=v,sz[u]-=sz[v],val[v]=0;
            s.pop();
        }
    }
}
using namespace BCJ;
struct Edge{
    int u,v,l,r;
};
int Ans[MAXN];
void Solve(int l,int r,vector<Edge> &A){
    vector<Edge>L,R;
    stack<P>s;//用来撤销的栈
    bool flag=true;
    int mid=(l+r)>>1;
    for (register int i=0;i<A.size();++i){
        if (A[i].l<=l&&r<=A[i].r){//只要记录跨越左右的边
            if (!Merge(A[i].u,A[i].v,s)){
                for (register int i=l;i<=r;++i) Ans[i]=0;//这样不用递归下去，因为都是0
                flag=false;
                break;
            }
        }
        else {
            if (A[i].l<=mid) L.push_back(A[i]);
            if (A[i].r>mid) R.push_back(A[i]);
        }
    }
    if (flag&&l<r){Solve(l,mid,L);Solve(mid+1,r,R);}
    Reverse(s);//回溯
}
int main(){
    int n=read(),m=read(),T=read();
    vector<Edge>A;
    for (register int i=1;i<=m;++i){
        int u=read(),v=read(),l=read(),r=read();
        A.push_back(Edge{u,v,l+1,r});
    }
    Init(n);
    for (register int i=1;i<=T;++i) Ans[i]=true;
    Solve(1,T,A);
    for (register int i=1;i<=T;++i) puts(Ans[i]?"Yes":"No");
}

总结：这类和时间/区间有关的题目大多数要用到线段树分治。

相关文章
P3302 [SDOI2013]森林BZOJ 4668 冷战CF145E Lucky Queries 线段树CF280D k-Maximum Subsequence Sum 线段树基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/86905927.html

更新于：2022年6月14日

题解

线段树

分治

并查集

启发式合并

评论