[HNOI 2019] 校园旅行

#LOJ 3057.

看到有个$m\leq 10^4$的部分分,就可以开始考虑$O(m^2)$暴力了。用$f_{x, y}$记录一下是否可以从$x$走回文路径走到$y$,之后对每对$f_{x, y}=1$的点对$x, y$,枚举他们的出边进行转移,整个转移用bfs实现即可。

对于所有的数据,$m$太大了,但是如果能降到$n$的规模就是吼的。

对于所有连接两个0点的边构成的联通块,如果这个联通块是一个二分图,那么每次转移就是在二分图上一个黑点一个白点一个黑点一个白点交替行走的,只要保留一棵生成树就好了。而如果不是二分图,就相当于有一个奇环,最简单的方法就是在联通块上的一个点上连一个自环,就搞出来奇环了。

对于所有连接两个1点的边构成的联通块也是如此。

对于所有连接一个0点和一个1点的联通块,很显然都是二分图,那么就直接连一个生成树就可以了

这个重新建出来的图很显然边只有$O(n)$条,那么就可以直接做了

#include <iostream>
#include <cstdio>
#include <cstring>

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

struct Graph{
    int cnt, to[1000010], ne[1000010], head[5010];
    void add_edge(int x, int y){
        to[++cnt]=y, ne[cnt]=head[x], head[x]=cnt;
        to[++cnt]=x, ne[cnt]=head[y], head[y]=cnt;
    }
    int operator [](int x){
        return head[x];
    }
}G1, G2;
int N, M, Q, val[5010], col[5010], qx[25000010], qy[25000010], h=1, t;
bool fl, f[5010][5010];

void add(int x, int y){
    if(f[x][y]) return;
    f[x][y]=f[y][x]=true;
    qx[++t]=x, qy[t]=y;
}

void dfs(int x, int fa, int opt){
    for(int i=G1[x]; i; i=G1.ne[i]) if(val[G1.to[i]]==opt){
        if(col[G1.to[i]]==col[x])
            fl=true;
        else if(col[G1.to[i]]==-1){
            col[G1.to[i]]=col[x]^1;
            G2.add_edge(x, G1.to[i]);
            add(x, G1.to[i]);
            dfs(G1.to[i], x, opt);
        }
    }
}

void dfs(int x, int fa){
    col[x]=1;
    for(int i=G1[x]; i; i=G1.ne[i]) 
        if(!col[G1.to[i]] && val[x]!=val[G1.to[i]]){
            G2.add_edge(x, G1.to[i]);
            dfs(G1.to[i], x);
        }
}

int main(){
    in(N); in(M); in(Q);
    for(int i=1; i<=N; i++){
        char c=getchar();
        while(c<'0'||c>'1') c=getchar();
        val[i]=c-'0';
    }
    for(int i=1, x, y; i<=M; i++){
        in(x); in(y);
        G1.add_edge(x, y);
    }
    for(int i=0; i<2; i++){
        memset(col, -1, sizeof(col));
        for(int j=1; j<=N; j++) if(col[j]==-1 && val[j]==i){
            fl=false; col[j]=0;
            dfs(j, 0, i);
            if(fl) G2.add_edge(j, j);
        }
    }
    memset(col, 0, sizeof(col));
    for(int i=1; i<=N; i++) if(!col[i])
        dfs(i, 0);
    for(int i=1; i<=N; i++) add(i, i);
    while(h<=t){
        int x=qx[h], y=qy[h]; h++;
        for(int i=G2[x]; i; i=G2.ne[i])
            for(int j=G2[y]; j; j=G2.ne[j]) if(val[G2.to[i]]==val[G2.to[j]])
                add(G2.to[i], G2.to[j]);
    }
    for(int i=1, x, y; i<=Q; i++){
        in(x); in(y);
        puts(f[x][y] ? "YES" : "NO");
    }
    return 0;
}
标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注