【HNOI2019】校园旅行 | Mrsrz's blog

DP，BFS，优化建图

题目大意：

给定一张简单无向图，每个点的权值为 $0$ 或 $1$。

每次询问给出两点，问是否存在一条连接两点的路径（可以不是简单路径），其经过的点的权值按经过顺序排列后，形成回文串。

题解：

$n$ 比较小，我们直接令 $f[x][y]$ 表示 $x$ 到 $y$ 是否存在这样的路径。用 BFS 进行转移，每次枚举两个端点相连的点。

这样的时间复杂度为 $O(n^2+m^2+q)$。

我们需要优化建图。

观察到，往回文串两边放相同的数时，只需要能够使它们奇偶性相同即可。因为另外一端可以在一条边上一直来回。考虑如何建图能在不改变可行的奇偶性的条件下，减少边数。

考虑把连接两个同色点的边，和连接两个异色点的边分开考虑。

对于连接同色的点的边形成的每个连通块，如果这个连通块是个二分图，那么从一个点到另一个点的奇偶性都是唯一确定的。任意取它的一棵生成树不改变其奇偶性。如果不是二分图，其中必定存在奇环，那么不管奇还是偶，都可以去那个奇环上转一圈来达到改变奇偶性的目的。那么我们仍然取生成树，再在任意一个点上，连一个自环，就可以达到相同目的。

对于连接异色点的边形成的连通块，由于它本身就是个二分图，直接取生成树即可。

那么我们就把边数降为了 $O(n)$ 级别。

再跑上面的算法，时间复杂度就是 $O(n^2+m+q)$。

在 UOJ 上要通过 Hack 数据还需要一定的常数优化。比如 $f[x][y]$ 和 $f[y][x]$ 是一样的，只需要算其中一个，这里可以优化一半的常数。

Code：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=5050;
vector<int>G[N];
char s[N];
int n,m,Q;
inline void AddEdgE(int u,int v){
    G[u].push_back(v);
    if(u!=v)G[v].push_back(u);
}
struct workspace{
    vector<int>G[N];
    bool vis[N];
    int dep[N];
    inline void addedge(int u,int v){G[u].push_back(v),G[v].push_back(u);}
    bool check(int now){
        for(int to:G[now])
            if(!dep[to]){
                dep[to]=dep[now]+1;
                bool ret=check(to);
                if(ret)return 1;
            }else
                if((dep[now]-dep[to]+1)&1)return 1;
        return 0;
    }
    void getedge(int now){
        vis[now]=1;
        for(int to:G[now])
            if(!vis[to]){
                AddEdgE(now,to);
                getedge(to);
            }
    }
    void work_1(){
        for(int i=1;i<=n;++i)
            if(!vis[i]){
                dep[i]=1;
                bool is_2=check(i);
                getedge(i);
                if(is_2)AddEdgE(i,i);
            }
    }
    void work_2(){
        for(int i=1;i<=n;++i)
            if(!vis[i])getedge(i);
    }
}A,B;
bool f[N][N];
int q[N*N];
void work(){
    int head=1,tail=0;
    for(int i=1;i<=n;++i){
        f[i][i]=1;
        q[++tail]=i<<16|i;
    }
    for(int i=1;i<=n;++i)
        for(int to:G[i])
            if(s[i]==s[to]&&!f[to][i]){
                f[i][to]=1;
                q[++tail]=i<<16|to;
            }
    while(head<=tail){
        int X=q[head++];
        int u=X>>16,v=X&65535;
        for(int x:G[u])
            for(int y:G[v])
                if(s[x]==s[y]&&!f[x][y]&&!f[y][x]){
                    f[x][y]=1;
                    q[++tail]=x<<16|y;
                }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q>>(s+1);
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        if(s[u]!=s[v])B.addedge(u,v);else A.addedge(u,v);
    }
    A.work_1(),B.work_2();
    work();
    while(Q--){
        int x,y;
        cin>>x>>y;
        cout<<(f[x][y]||f[y][x]?"YES\n":"NO\n");
    }
    return 0;
}