BZOJ4025 二分图

发表于

  题意: 给你一个图中每个点出现与消失的时刻，求在每一个时刻中该图是否为二分图。

  这道题可以说是LCT维护动态生成树的集大成题。其中加入了二分图模型，对于以后很多的题目都具有启示意义。
  对于这道题，我们考虑维护以删除时间为关键字的最大生成树。对于整个图来说，就是一个最大生成森林。

  在每一时刻，在生成森林中，对于每一条出现的边:
  如果该边两端不联通，则加入该边。
  如果该边两端联通，将该边连上后会出现一个环。
  如果这个环是奇环，那么将该环中删除时间最早(权值最小)的边删除，并加入标记集合，表示该边存在时，图不为二分图。
  具体实现的话，就是先将出现边与原路径中的最小边比较，如果比最小边要小，则直接判断是否为奇环加标记即可。
  如果比最小边要大，那么就删除最小边，连接上该边，将最小边拿去判断。

  对于每一条删除的边:
  如果这条边在树上，直接cut。
  如果这条边在删除集合里，直接去掉。

  每一个时刻，当且仅当集合内没有元素时，图为二分图。

  维护生成树中最小/大边，我采用的是维护指针的方法。指针减去初指针就为实际下标了。
  判断是否为奇环，就维护LCT的size即可。注意边的size设为0。
  注意这道题的联通性不能用普通并查集，因为有cut操作。我直接暴力判断的联通性。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define mp make_pair
#define ms(a, b) memset(a, b, sizeof a)
#define pb push_back
#define SZ(x) (int((x).size()))
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x) {
	static char c; bool flag = 0;
	while(!isdigit(c = getchar())) if(c == '-') flag = 1;
	for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
	if(flag) x = -x; return x;
}
const int maxn = 100010, maxm = 200010, INF = 0x3f3f3f3f;
struct node
{
    node *p, *c[2], *Min;
    bool rev, isdot;
    int val, sz;
    node(): p(0), Min(this), rev(0), val(INF) { c[0] = c[1] = 0; }
    void setc(node* o, bool b) { c[b] = o; if(o) o->p = this; }
    bool isroot() { return !p || p->c[0] != this && p->c[1] != this; }
    bool getpos() { return p->c[1] == this; }
    void updrev() { rev ^= 1; }
    void pushup()
    {
        Min = this;
        rep(i, 0, 1) if(c[i] && c[i]->Min->val < Min->val) Min = c[i]->Min;
        sz = isdot;
        rep(i, 0, 1) if(c[i]) sz += c[i]->sz;
    }
    void pushdown()
    {
        if(rev)
        {
            rep(i, 0, 1) if(c[i]) c[i]->updrev();
            swap(c[0], c[1]); rev = 0;
        }
    }
    void rot()
    {
        node* f = p; bool b = getpos();
        if(f->isroot()) p = f->p;
        else f->p->setc(this, f->getpos());
        f->setc(c[!b], b); setc(f, !b);
        f->pushup();
    }
    void relax() { if(!isroot()) p->relax(); pushdown(); }
    void splay()
    {
        for(relax(); !isroot(); rot())
            if(!p->isroot()) (p->getpos() == getpos() ? p : this)->rot();
        pushup();
    }
    void access()
    {
        for(node *u = this, *v = 0; u; v = u, u = u->p)
            u->splay(), u->setc(v, 1), u->pushup();
        splay();
    }
    void beroot() { access(); updrev(); }
}nd[maxn + maxm];
int n, m, t;
namespace LCT
{
    bool check(int x, int y)
    {
        node *u = nd + x, *v = nd + y;
        while(u->p) u = u->p;
        while(v->p) v = v->p;
        return u == v;
    }
    void link(int x, int y)
    {
        node *u = nd + x, *v = nd + y;
        u->beroot(); u->p = v;
    }
    void cut(int x, int y)
    {
        node *u = nd + x, *v = nd + y;
        u->beroot(); v->access();
        u->p = v->c[0] = NULL; v->pushup();
    }
    node* query(int x, int y)
    {
        node *u = nd + x, *v = nd + y;
        u->beroot(); v->access();
        return v->Min;
    }
}
using namespace LCT;
struct edge
{
    int u, v, w;
}E[maxm];
vector<int> Add[maxn], Del[maxn];
int cnt;
bool inTree[maxm], inSet[maxm];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
    read(n); read(m); read(t); int st, ed;
    rep(i, 1, m)
    {
        read(E[i].u), read(E[i].v), read(st), E[i].w = read(ed);
        Add[st].pb(i); Del[ed].pb(i);
    }
    rep(i, 1, n) (nd + i)->isdot = (nd + i)->sz = 1;
    rep(i, 1, m)
    {
        (nd + n + i)->val = E[i].w;
        (nd + n + i)->isdot = (nd + n + i)->sz = 0;
    }
    rep(k, 0, t - 1)
    {
        rep(i, 0, SZ(Add[k]) - 1)
        {
            int j = Add[k][i];
            if(E[j].u == E[j].v) { inSet[j] = 1; ++cnt; continue; }
            if(!check(E[j].u, E[j].v))
            {
                link(E[j].u, j + n);
                link(E[j].v, j + n);
                inTree[j] = 1;
            }
            else
            {
                node* o = query(E[j].u, E[j].v);
                int h = o - nd - n;
                if(E[j].w > o->val)
                {
                    if((nd + E[j].v)->sz & 1) inSet[h] = 1, ++cnt;
                    cut(E[h].u, h + n);
                    cut(E[h].v, h + n);
                    link(E[j].u, j + n);
                    link(E[j].v, j + n);
                    inTree[h] = 0; inTree[j] = 1;
                }
                else if((nd + E[j].v)->sz & 1) inSet[j] = 1, ++cnt;
            }
        }
        rep(i, 0, SZ(Del[k]) - 1)
        {
            int j = Del[k][i];
            if(inTree[j]) inTree[j] = 0, cut(E[j].u, j + n), cut(E[j].v , j + n);
            if(inSet[j]) inSet[j] = 0, --cnt;
        }
        puts(cnt ? "No" : "Yes");
    }
    return 0;
}