DP+生成树-[HNOI2019]校园旅行-解题报告

· · 个人记录

不知道复杂度如何证明...

首先，有一个很好想到的暴力DP：记录每个pair的可达性，转移的话暴力每个两个点的出边，看颜色是否相同。

这样复杂度据说是O(m^2)的。

然后就是很有意思的一个结论：

我们先只考虑连接相同颜色的边，形成若干联通块，对于每个联通块，如果是二分图，那么我们保留任意一棵生成树即可。否则，我们随意选一个点连自环。

对于颜色不同的边，也求出生成树，这一定是二分图。

原因是，对于一个回文串，例如000111000，我们可以拆成3部分，由于我们可以通过反复走来改变长度，所以我们只关心长度的奇偶性和切换次数的奇偶性。

这样边数就减少到O(n)级别了。

#define N 5005
int n,m;
vector<int>G[N],E[N];
bool w[N];
bool hv;
int dep[N];
void dfs(int x)
{
    for(solid v:G[x])
    {
        if(w[x]!=w[v]) continue;
        if(dep[v])
        {
            if((dep[v]^dep[x]^1)&1) hv=1;
            continue;
        }
        E[x].pb(v),E[v].pb(x),dep[v]=dep[x]+1;
        dfs(v);
    }
}
bool vis[N];
void efs(int x)
{
    vis[x]=1;
    for(solid v:G[x])
    {
        if(vis[v]||w[x]==w[v]) continue;
        E[x].pb(v),E[v].pb(x);
        efs(v);
    }
}
bool dp[N][N];
queue< pii > q;
il void ins(int a,int b)
{
    if(a>b) swap(a,b);
    if(!dp[a][b]) dp[a][b]=1,q.push(mp(a,b));
}
void prework()
{
    for(ri i=1; i<=n; ++i) if(!dep[i])
        {
            dep[i]=1,hv=0;
            dfs(i);
            if(hv) E[i].pb(i);
        }
    for(ri i=1; i<=n; ++i) if(!vis[i]) efs(i);
    for(ri i=1; i<=n; ++i) ins(i,i);
    while(!q.empty())
    {
        int x=q.front().fi,y=q.front().se; q.pop();
        for(solid u:E[x])
            for(solid v:E[y])
                if(w[u]==w[v]) ins(u,v);
    }
}
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("ot.out","w",stdout);
#endif
    int cq,a,b; in(n,m,cq);
    static char tc[N]; scanf("%s",tc+1);
    for(ri i=1; i<=n; ++i) w[i]=tc[i]&1;
    for(ri i=1; i<=m; ++i)
    {
        in(a,b);
        G[a].pb(b),G[b].pb(a);
        if(w[a]==w[b]) ins(a,b);
    }
    prework();
    while(cq--)
    {
        in(a,b);
        if(a>b) swap(a,b);
        puts(dp[a][b]?"YES":"NO");
    }
    return 0;
}