Menu
April 26, 2015

BZOJ 4025: 二分图

Solution

  • 离线动态图有个经典做法,对时间轴分治+可持久化并查集,时间复杂度,然而本题并不能过。

  • 本题可以采用xyz在WC2015讲的维护删除时间最大生成树的方法。

  • 由于要判断是否为二分图,我们统计有多少条边满足:在这条边被删除之前图一定不是二分图

  • 考虑加边,设权值为

    1. 原本不连通:直接连接就好。
    2. 原本联通且:
      • 若当前边与形成偶环,直接无视这条边
      • 若当前边与形成奇环,显然在这条边删除之前图一定不是二分图,标记这条边。
    3. 原本联通且:
      • 断开环上的最小边,连上当前边,对最小边做第二种情况。
  • 考虑删除

    1. 若为树边,显然删除不会有影响,直接删除。
    2. 否则删除这条边上的标记。
  • 询问时,只要看当前标记数量是否为0即可,为0则是二分图。

  • 最大生成树用 Link-Cut Tree 维护,不会LCT的看LCT 的WiKi百科和论文《QTREE解法的一些研究》,没写过可以上VFleaKing的博客找代码库学一学。


代码:

4025.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
inline void readi(int &x);
const int maxn=100005,maxm=200005,inf=(1<<25)-1;

template<class T> inline bool ten(T &x,const T &y){return y<x?(x=y,1):0;}
template<class T> inline bool rel(T &x,const T &y){return x<y?(x=y,1):0;}

int n,m,T,opn,cnt;

struct edge
{
    int u,v,s,e;
}e[maxm];

int it[maxm],od[maxm];

pair<int,int> opt[maxm*2];

struct node
{
    bool rev;
    int val,mn,siz;
    node *lc,*rc,*f;
    inline void tagrev()
    {rev^=1,swap(lc,rc);}
    inline void update()
    {
        mn=val,siz=1;
        if(lc)ten(mn,lc->mn),siz+=lc->siz;
        if(rc)ten(mn,rc->mn),siz+=rc->siz;
    }
    inline void downdate()
    {
        if(rev)
        {
            if(lc)lc->tagrev();
            if(rc)rc->tagrev();
            rev=0;
        }
    }
    inline bool isroot()
    {return !f||f->lc!=this&&f->rc!=this;}
}ndl[maxn],edl[maxm];

inline void rotate(node *x)
{
    node *y=x->f,*z=y->f,*b=y->lc==x?x->rc:x->lc;
    y->f=x,x->f=z;
    if(b)b->f=y;
    if(z)
    {
        if(z->lc==y)z->lc=x;
        else if(z->rc==y)z->rc=x;
    }
    if(y->lc==x)y->lc=b,x->rc=y;
    else y->rc=b,x->lc=y;
    y->update();
}

void splay(node *x)
{
    static node* stt[maxm*3];
    int stn=1;
    stt[1]=x;
    for(node *i=x;!i->isroot();i=i->f)stt[++stn]=i->f;
    while(stn)stt[stn--]->downdate();
    while(!x->isroot())
    {
        if(x->f->isroot())rotate(x);
        else if((x->f->f->lc==x->f)==(x->f->lc==x))rotate(x->f),rotate(x);
        else rotate(x),rotate(x);
    }
    x->update();
}

void access(node *x)
{
    for(node *p=x,*q=NULL;p;q=p,p=p->f)
    {
        splay(p);
        p->rc=q;p->update();
    }
}

inline node* findroot(node *x)
{
    access(x);
    splay(x);
    while(x->downdate(),x->lc)x=x->lc;
    splay(x);
    return x;
}

inline void makeroot(node *x)
{
    access(x);
    splay(x);
    x->tagrev();
}

inline void link(node *x,node *y)
{
    makeroot(x),makeroot(y);
    x->f=y;
}

inline void cut(node *x,node *y)
{
    makeroot(x),access(y);
    splay(y);
    y->lc=x->f=NULL;
    y->update();
}

inline void link(const int &i)
{
    link(edl+i,ndl+e[i].u);
    link(edl+i,ndl+e[i].v);
    it[i]=1;
}

inline void cut(const int &i)
{
    cut(edl+i,ndl+e[i].u);
    cut(edl+i,ndl+e[i].v);
    it[i]=0;
}

node* getmin(node *x)
{
    int t=x->mn;
    while(x->val!=t)
    {
        x->downdate();
        if(x->lc&&x->lc->mn==t)x=x->lc;
        else x=x->rc;
    }
    splay(x);
    return x;
}

void addedge(const edge &e,const int &i)
{
    if(findroot(ndl+e.u)!=findroot(ndl+e.v))
    {
        link(i);
        return;
    }
    node *x=ndl+e.u,*y=ndl+e.v,*z;
    makeroot(x),access(y),splay(y);
    z=getmin(y);
    int sz=z->siz;
    if(e.e>z->val)
    {
        int j=z-edl;
        cut(j);
        if(!((sz>>1)&1))cnt+=od[j]=1;
        link(i);
    }
    else
        if(!((sz>>1)&1))cnt+=od[i]=1;
}

void deledge(const int &i)
{
    if(it[i]){cut(i);return;}
    if(od[i])cnt--,od[i]=0;
}

void init()
{
    readi(n),readi(m),readi(T);
    for(int i=1;i<=n;i++)
        ndl[i].val=ndl[i].mn=inf,ndl[i].siz=1;
    for(int i=1;i<=m;i++)
    {
        readi(e[i].u),readi(e[i].v),readi(e[i].s),readi(e[i].e);
        edl[i].val=edl[i].mn=e[i].e,edl[i].siz=1;
        if(e[i].s!=e[i].e)
            opt[++opn]=make_pair(e[i].s,i);
            opt[++opn]=make_pair(e[i].e,i);
    }
    sort(opt+1,opt+opn+1);
}

void work()
{
    for(int i=1,p=1,t,w;i<=T;i++)
    {
        for(;p<=opn&&(t=opt[p].first)<i;p++)
        {
            w=opt[p].second;
            if(t==e[w].s)addedge(e[w],w);
            else deledge(w);
        }
        puts(cnt?"No":"Yes");
    }
}

int main()
{
    init();
    work();
    return 0;
}

inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}

 
comments powered by Disqus