BZOJ4025 二分图

题意

​ 给你一些边,这些边在只能在某段时间出现,问每一个时刻出现的边构成的是否是二分图(没有边的个数为奇数的环)。

题面

http://www.lydsy.com/JudgeOnline/problem.php?id=4025

题解

​ 考虑如果得到某个时刻的生成树,那么对于所有非树边,如果都无法和树边形成奇环,那么一定是不可能出现奇环的。这个应该很好理解。

​ 考虑用LCTLCT来维护这个生成树,为了防止去掉一条边之后还要其它边来替代,我们维护时间的最大生成树,统计每个点提供的奇环个数。然后动态删除。

O(nlogn)O(n log n)

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f,oo = inf;
#define pc putchar
#define RG register
#ifdef LOCAL
char __wzp[1<<15|1],*__S=__wzp+32768;
#define gc() (__S>=__wzp+32768?(__wzp[fread(__wzp,sizeof(char),1<<15,stdin)]=EOF),*((__S=__wzp)++):*(__S++))
#else
#define gc getchar
#endif
inline ll read(){
RG ll x=0,f=1;RG char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(ll x){
if(x<0)x=-x,pc('-');if(x>=10)write(x/10);pc(x%10+'0');
}
void writeln(ll x){
write(x);puts("");
}
#define rd read
#define mem(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define mp make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define Rep(i,a,b) for(RG int i=(a);i<=(b);++i)
#define Down(i,a,b) for(RG int i=(a);i>=(b);--i)
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".in","w",stdout);}
#define y1 _________y1
#define hash _____hash
#define union ___union
const int maxn = 200005;
const int maxnode = 300005;
struct Edge{
int u,v,t,opt,id;
Edge(){}
Edge(int u,int v,int t,int opt,int id):u(u),v(v),t(t),opt(opt),id(id){}
bool operator < (const Edge &w) const{
return t<w.t;// || t==w.t && opt > w.opt;
}
}edge[maxn*2];int nume;
int flag[maxn],tree[maxn],l[maxnode],r[maxnode],pos[maxnode],Ipos[maxnode],val[maxnode];
int f[maxnode],c[maxnode][2],size[maxnode],rev[maxnode],mn[maxnode],fa[maxnode];
bool isroot(int x){
return (c[fa[x]][0]!=x) && (c[fa[x]][1]!=x);
}
void pushdown(int x){
if(!x)return;
if(rev[x]){
swap(c[x][0],c[x][1]);
rev[c[x][0]]^=1;
rev[c[x][1]]^=1;
rev[x]=0;
}
}
void down(int x){
if(!isroot(x)) down(fa[x]);
pushdown(x);
}
void pushup(int x){
size[x] = 1;mn[x] = x;
if(c[x][0]){
size[x] += size[c[x][0]];
if(val[mn[c[x][0]]] < val[mn[x]]) mn[x] = mn[c[x][0]];
}
if(c[x][1]){
size[x] += size[c[x][1]];
if(val[mn[c[x][1]]] < val[mn[x]]) mn[x] = mn[c[x][1]];
}
}
void rotate(int x){
int y = fa[x],k = c[y][0] == x;
if(!isroot(y)) c[fa[y]][c[fa[y]][1]==y] = x;fa[x] = fa[y];
c[y][!k] = c[x][k];fa[c[y][!k]] = y;
c[x][k] = y;fa[y] = x;
pushup(y);pushup(x);
}
void splay(int x){
down(x);
for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])
if(!isroot(y)) rotate((c[fa[y]][0]==y)==(c[y][0]==x)?y:x);
}
void access(int x){
for(int t=0;x;t=x,x=fa[x])
splay(x),c[x][1]=t,pushup(x);
}
void mroot(int x){
access(x);
splay(x);
rev[x]^=1;
}
void link(int x,int y){
mroot(x),fa[x]=y;
}
void cut(int x,int y){
mroot(x),access(y),splay(y);
fa[x]=c[y][0]=0;
}
int find(int x){
access(x),splay(x);
while(c[x][0])x=c[x][0];
return x;
}
int cnt=0;//奇环的总个数!!!
int sz;
void add(int i){
int u = edge[i].u,v = edge[i].v,t = edge[i].opt,id = edge[i].id;
if(u==v){
flag[id] = 1;
++cnt;
return ;
}
if(find(u) == find(v)){
//同一个连通块,要删除原来树上
mroot(u);
access(v);
splay(v);//y的子树维护的是x~y路径上的边!
int w = mn[v];
int num = size[v] >> 1;
if(val[w] >= t){//不换
if(!(num&1)){
++cnt;
flag[id] = 1;
}
return;
} else{//换成这条边
if(!(num&1)){
++cnt;
flag[pos[w]] = 1;
}
cut(w,l[w]);
cut(w,r[w]);
tree[pos[w]] = 0;
}
}
++sz;
val[sz] = t;
l[sz] = u,r[sz] = v;
pos[sz] = id;Ipos[id] = sz;
link(sz,u);link(sz,v);
tree[id] = true;
}
int n,m,T;
int main(){
n = rd(),m = rd(),T = rd();
Rep(i,1,m){
int u = rd(),v=rd(),st=rd(),ed = rd();
if(u>v)swap(u,v);
edge[nume++] = Edge(u,v,st,ed,i);
edge[nume++] = Edge(u,v,ed,-1,i);
}
sort(edge,edge+nume);
mem(val,0x3f);
sz = n;
int j = 0;
rep(i,0,T){
for(;j<nume&&edge[j].t==i;j++){
if(edge[j].opt == -1){
if(tree[edge[j].id]){//如果是生成树上的边
cnt -= flag[edge[j].id];
flag[edge[j].id] = 0;
tree[edge[j].id] = false;
cut(Ipos[edge[j].id],l[Ipos[edge[j].id]]);
cut(Ipos[edge[j].id],r[Ipos[edge[j].id]]);
} else{
cnt -= flag[edge[j].id];//cnt表示有多少个奇环
flag[edge[j].id] = 0;
}
} else{
add(j);
}
}
puts(cnt?"No":"Yes");
}
}

然后网上有更好的CDQ分治的小常数短代码做法,时间复杂度2只log。

具体考虑对时间分治,如果某个时间段完整地包含了一些边出现的时间,那么把边用DSU加进去,如果出现奇环(可以直接用到这个的祖先的dis来xor一下),那么整个时间段都是有奇环的,否则继续递归,然后要恢复,那么用按秩合并并查集来维护。

O(nlog2n)O(n log^2n)

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f,oo = inf;
#define pc putchar
#define RG register
#ifdef LOCAL
char __wzp[1<<15|1],*__S=__wzp+32768;
#define gc() (__S>=__wzp+32768?(__wzp[fread(__wzp,sizeof(char),1<<15,stdin)]=EOF),*((__S=__wzp)++):*(__S++))
#else
#define gc getchar
#endif
inline ll read(){
RG ll x=0,f=1;RG char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(ll x){
if(x<0)x=-x,pc('-');if(x>=10)write(x/10);pc(x%10+'0');
}
void writeln(ll x){
write(x);puts("");
}
#define rd read
#define mem(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define mp make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define Rep(i,a,b) for(RG int i=(a);i<=(b);++i)
#define Down(i,a,b) for(RG int i=(a);i>=(b);--i)
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".in","w",stdout);}
#define y1 _________y1
#define hash _____hash
#define union ___union
const int maxn = 200005;
const int maxnode = 300005;
struct Edge{
int u,v,st,ed;
Edge(){}
Edge(int u,int v,int st,int ed):u(u),v(v),st(st),ed(ed){}
};
int fa[maxn],c[maxn],rank[maxn],s[maxn*2],top;
int dis(int x){//x到root的距离
if(fa[x]==x||!fa[x]) return 0;
return c[x]^dis(fa[x]);
}
int getfa(int x){
if(fa[x]==x) return x; else return getfa(fa[x]);
}//按秩合并
void union(int x,int y,int w){
if(rank[x] > rank[y]) swap(x,y);
if(rank[x]==rank[y]){s[++top] = -y;rank[y]++;}
//使得rank[x] < rank[y]
//x合并到y
fa[x] = y;c[x] = w;
s[++top] = x;
}
void restore(int ppp){
while(top > ppp){
if(s[top] < 0) rank[-s[top]]--; else{
fa[s[top]] = s[top];
c[s[top]] = 0;
}
top--;
}
}
void CDQ(int l,int r,vector<Edge> &E){
int mid = (l+r)>>1;
int pre = top;
vector<Edge> L,R;
int sz = E.size();
for(int i=0;i<sz;i++){
if(E[i].st == l && E[i].ed==r){//加入这条边
int x = E[i].u,y = E[i].v;
int fx = getfa(x),fy = getfa(y);
if(fx!=fy)
union(fx,fy,dis(x)^dis(y)^1);
else
if((dis(x)^dis(y)^1)&1){//有奇环
Rep(j,l,r)puts("No");
restore(pre);
return;
}
} else{
//拆分
if(E[i].ed <= mid) L.pb(E[i]); else
if(mid+1<=E[i].st) R.pb(E[i]); else{
L.pb(Edge(E[i].u,E[i].v,E[i].st,mid));
R.pb(Edge(E[i].u,E[i].v,mid+1,E[i].ed));
}
}
}
if(l==r){
puts("Yes");
restore(pre);
return;
}
CDQ(l,mid,L);
CDQ(mid+1,r,R);
restore(pre);
}
int n,m,T;
int main(){
vector<Edge> e;
n = rd(),m = rd(),T = rd();
Rep(i,1,n) fa[i]=i,rank[i]=0,c[i]=0;
Rep(i,1,m){
int u = rd(),v=rd(),st=rd(),ed = rd();
st++;
if(st<=ed)e.pb(Edge(u,v,st,ed));
}
CDQ(1,T,e);
return 0;
}
文章目录
  1. 1. 题意
  2. 2. 题面
  3. 3. 题解