Luogu

BZOJ

LOJ

UOJ 我又没有过Extra Test

分析

广告:myy的题解

myy的又一道神仙题...

$30$ 分的 $\mathrm{dp}$ 很容易想(并不,我就没想到:设 $f[x][y]$ 表示 $x$ 能否到 $y$ ,然后枚举出边转移即可。时间复杂度 $O(m^2)$ 。

这个做法只有 $30$ 分的原因是边数太多了,考虑怎么优化边数。

对于连接所有同色点的边,每个连通块内保留一棵生成树即可。另外,如果这个连通块不是二分图,那么还需要加一个自环。

对于所有连接异色点的边,做同样的事情。

可以发现这样子不会影响答案。 证明不会

这样子边数就是 $O(n)$ 级别的了,时间复杂度为 $O(n^2)$ 。

代码

不知道为什么常数特别大...

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;
const int M=10000+10;

vector<int> E[3][N];

struct Edge { int v,nxt; } e[M<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
    e[++cnt]=(Edge){u,head[v]},head[v]=cnt;
}

char s[N];
int col[N],fa[N],sta[N],top,flag;
int f[N][N];

inline void dfs(int u,int c,int k){
    sta[++top]=u,col[u]=c;
    for (re int v:E[k][u]){
        if (!col[v]) fa[v]=u,dfs(v,3-c,k);
        else if (col[v]!=3-c) flag=1;
    }
}

struct node { int x,y; };
queue<node> Q;

int main() {
    int n=read(),m=read(),q=read(); scanf("%s",s+1);
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),k=(s[u]==s[v])?(s[u]-'0'+1):0;
        E[k][u].push_back(v),E[k][v].push_back(u);
    }
    
    for (re int k=0;k<3;++k) {
        memset(col,0,sizeof(col));
        for (re int i=1;i<=n;++i) {
            if (col[i]) continue;
            top=flag=0,dfs(i,1,k);
            for (re int j=2;j<=top;++j) addEdge(sta[j],fa[sta[j]]);
            if (flag) addEdge(i,i);
        }
    }
    
    for (re int i=1;i<=n;++i) {
        f[i][i]=1,Q.push((node){i,i});
        for (re int j=head[i];j;j=e[j].nxt) {
            int v=e[j].v;
            if (s[i]==s[v]) f[i][v]=1,Q.push((node){i,v});
        }
    }
    while (!Q.empty()) {
        int x=Q.front().x,y=Q.front().y; Q.pop();
        for (re int i=head[x];i;i=e[i].nxt)
            for (re int j=head[y];j;j=e[j].nxt) {
                int v1=e[i].v,v2=e[j].v; if (f[v1][v2]) continue;
                if (s[v1]==s[v2]) f[v1][v2]=1,Q.push((node){v1,v2});
            }
    }

    while (q--) {
        int x=read(),y=read();
        puts(f[x][y]?"YES":"NO");
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 43 PM