Chlience

【题解】BZOJ 4025 二分图
Problem传送门 >ω<题目大意:给定一个 $n$ 个点的图和 $m$ 条边,每条边有其出现和结束时间,问在 ...
扫描右侧二维码阅读全文
05
2018/12

【题解】BZOJ 4025 二分图

Problem

传送门 >ω<

题目大意:

给定一个 $n$ 个点的图和 $m$ 条边,每条边有其出现和结束时间,问在 $1-t$ 的每个时刻该图是不是二分图

Solution

记得很久之前好像做过一道类似的题呢,找不到了...

首先是判断二分图的问题,若一个图中出现奇环,那么这个图不是二分图;反之,这个图是二分图
那么在当前图是合法二分图的情况下加入边 $(u,v)$

  • 若 $(u,v)$ 没有联通

    • 连接 $u,v$
  • 若 $u,v$ 已经联通

    • 显然的,$u,v$ 之间所有路径的奇偶性必然一致,否则该图不是合法二分图
    • 那么如果两点间的路径长度为奇数,加入 $(u,v)$ 后没有出现奇环
    • 如果两点间的路径长度为偶数,加入 $(u,v)$ 后出现奇环,该图将不是二分图

删除操作就非常的不好做

考虑去掉删除操作,一般来说,直接使用 时间线段树 即可
将每条边以区间更新树上 $[begin,end]$ 区间的形式打上标记,每个叶子节点处的图就是根节点到叶子节点路径上的所有边的集合,这样就绕过了删除操作

那么用带权并查集来维护两点之间距离的奇偶性,这样便能统计是否合法

这时候发现时间复杂度仍然不是很优秀,如何优化?

每次在查询根节点到不同叶子节点的路径时,其实大部分的节点都被重复计算了,那么能不能做到 $DFS$ 一样每个节点值访问一遍呢?

当然是可以的
那么就要考虑撤销一个点所包含的边对图的影响

如果是一张无向图,其撤销操作就很复杂,如果是一片森林呢?

  • 若 $(u,v)$ 之间已经联通

    • 加入该边合法,不加入(加入没有任何意义,无法改变奇偶性)
    • 加入该边不合法,不加入(不管怎么样其子树不可能使得该图重新合法,只需要打上不合法标记即可,并且退出该点时删除标记)
  • 若 $(u,v)$ 之间未联通

    • 连接 $(u,v)$ 并且记录下来,退出该点时删除该边

在树上删边就简单多了,因为之前用带权并查集维护连通性(奇偶性),只需要在不采用路径压缩的情况下,将该条边连接的两个点($u,v$ 当时的祖先节点)断开即可

为了保证复杂度,需要按秩合并,不再多说

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int M = 200010;
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
typedef pair<int, bool> p;
int n , m , t , ans;
struct edge {int u , v;};
struct tree {
    int head[N * 4 * 20];
    edge e[M * 20];
    int nxt[M * 20];
    int tot;
    int fa[N] , num[N];
    bool key[N];
    int sta[M * 20] , top;
    void clear() {
        for(int i = 1 ; i <= n ; ++ i) fa[i] = i;
        for(int i = 1 ; i <= n ; ++ i) num[i] = 1;
        for(int i = 1 ; i <= n ; ++ i) key[i] = 0;
    }
    p find(int x) {
        bool ans = 0;
        while(x != fa[x]) {
            ans ^= key[x];
            x = fa[x];
        }
        return p{x , ans};
    }
    void addedge(int x  , edge E) {
        ++ tot;
        e[tot] = E;
        nxt[tot] = head[x];
        head[x] = tot;
    }
    void insert(int x , int l , int r , int ll , int rr , edge E) {
        if(l >= ll && r <= rr) addedge(x , E);
        else {
            if(mid >= ll) insert(L , l , mid , ll , rr , E);
            if(mid < rr) insert(R , mid + 1 , r , ll , rr , E);
        }
    }
    void dfs(int x , int l , int r) {
        int flag = 0;
        int TOP = top;
        for(int i = head[x] ; i && !ans ; i = nxt[i]) {
            p fx = find(e[i].u) , fy = find(e[i].v);
            if(fx.first == fy.first) {
                if(fx.second == fy.second){
                    flag = 1;
                    ans = 1;
                }
            }
            else {
                if(num[fx.first] > num[fy.first]) swap(fx , fy);
                fa[fx.first] = fy.first;
                num[fy.first] += num[fx.first];
                if(fx.second == fy.second) key[fx.first] = 1;
                else key[fx.first] = 0;
                sta[++ top] = fx.first;
            }
        }
        if(l == r) puts(ans ? "No" : "Yes");
        else {
            dfs(L , l , mid);
            dfs(R , mid + 1 , r);
        }
        //删除加入的边
        if(flag) ans = 0;
        while(top > TOP) {
            int u = sta[top] , v = fa[u];
            num[v] -= num[u];
            fa[u] = u;
            key[u] = 0;
            sta[top --] = 0;
        }
    }
}T;
int main() {
    n = read(); m = read(); t = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int u = read() , v = read() , l = read() + 1 , r = read();
        T.insert(1 , 1 , t , l , r , edge{u , v});
    }
    T.clear();
    T.dfs(1 , 1 , t);
    return 0;
}
Last modification:December 5th, 2018 at 09:36 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment