题目链接

LOJ：https://loj.ac/problem/3057

洛谷：https://www.luogu.org/problemnew/show/P5292

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Solution

先膜一发\(myy\)，这里是官方题解。

对于\(30\)分，可以得到一个很显然的做法：设\(f[i][j]\)表示\(i\to j\)的答案，然后枚举\(i,j\)的出边转移，这样做是\(O(m^2)\)的。

对于\(100\)分，注意到点的规模没变，我们有一个缩边的想法。

我们把边分成三类，同色的两种和异色的一种，对每类分别建图，然后我们对每个联通块进行考虑：

  • 如果当前联通块是二分图，那么可以说明从\(i\)点到\(j\)点所经过的边数必然只能是奇数或偶数，那么我们任意处理出一棵生成树，容易发现这棵生成树和原图等价（如果这边多走了就在另一边来回走以抵消）。

  • 如果当前联通块不是二分图，那么边数可以是奇数或偶数，那么我们只需要在生成树任意加一个自环就好了。

缩完之后可以发现边数是\(O(n)\)级别的，那么我们套用上边的暴力，复杂度达到了\(O(n^2)\)，足已通过此题。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;

char s[maxn];
int n,m,Q,vis[maxn],sta[maxn],top,f[5050][5050],flag;

struct Graph {
    int head[maxn],tot,fa[maxn];
    struct edge{int to,nxt;}e[maxn*20];
    
    void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
    void ins(int u,int v) {add(u,v),add(v,u);}

    void dfs(int x,int c) {
        vis[x]=c,sta[++top]=x;
        for(int i=head[x];i;i=e[i].nxt)
            if(!vis[e[i].to]) dfs(e[i].to,3-c),fa[e[i].to]=x;
            else flag|=(vis[e[i].to]!=3-c);
    }

    void solve() {
        queue<pair<int,int > > q;
        for(int i=1;i<=n;i++) f[i][i]=1,q.push(make_pair(i,i));
        for(int x=1;x<=n;x++)
            for(int i=head[x];i;i=e[i].nxt)
                if(s[x]==s[e[i].to]) f[x][e[i].to]=1,q.push(make_pair(x,e[i].to));
        while(!q.empty()) {
            int x=q.front().first,y=q.front().second;q.pop();
            for(int i=head[x];i;i=e[i].nxt)
                for(int u,v,j=head[y];j;j=e[j].nxt)
                    if(s[u=e[i].to]==s[v=e[j].to])
                        if(!f[u][v]) f[u][v]=1,q.push(make_pair(u,v));
        }
    }
}g[3],t;

int main() {
    read(n),read(m),read(Q);scanf("%s",s+1);
    for(int i=1,x,y;i<=m;i++) {
        read(x),read(y);
        if(s[x]!=s[y]) g[0].ins(x,y);
        else if(s[x]=='1') g[1].ins(x,y);
        else g[2].ins(x,y);
    }
    for(int i=0;i<=2;i++) {
        memset(vis,0,sizeof vis);
        for(int j=1;j<=n;j++)
            if(!vis[j]) {
                top=flag=0,g[i].dfs(j,1);
                while(top) {
                    int x=sta[top];
                    if(g[i].fa[x]) t.ins(g[i].fa[x],x);top--;
                }if(flag) t.ins(j,j);
            }
    }
    t.solve();
    for(int i=1,x,y;i<=Q;i++) read(x),read(y),puts(f[x][y]?"YES":"NO");
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄