P5292 [HNOI2019]校园旅行 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Imakf
    orz
  • yzhang
    orz
  • _____hzf_____
    orz
  • Ender_zzm
    STO
作者: Mital 更新时间: 2019-04-08 19:37  在Ta的博客查看    8  

myy出的题真的好妙啊 $QAQ$

$HN-D2$全程没人切题欸。。。

首先是暴力的做法,我们可以发现,一个回文串会满足如下性质:

将首尾去掉其仍然回文。

所以我们可以根据这个性质来做,预处理出所有点对是否可以通过回文串达。

所以我们假设已经知道了$(x,y)$之间是回文串可达的,那么我们其实只需要枚举与$x$,$y$分别相连的两个点$(u,v)$,如果这两个点相同,那么这两个点便回文串可达。

具体做法是类似于$dp/spfa$的一个流程。会将所有单独的点加入一个队列,如果一条边连接了两个相同的点,那么也将这两个点加入队列。

那么每次弹出队列并更新即可,注意一个点对不需要去重复更新其他点多次,也就是说每个点对只会入队/出队一次。个人感觉这样做的复杂度应该是$O(N^2M)$,然而看了myy的题解这个复杂度是$O(M^2)?$

代码大致如下:

while( !q.empty() ) {
    Node u = q.front(); q.pop() ;
    int Fr = u.from, To = u.to ; 
    for( int i = head[Fr]; i; i = e[i].to ) {
        int v = e[i].to ; 
        for( int j = head[To]; j; j = e[j].to ) {
            int v2 = e[j].to ; 
            if( w[v] != w[v2] || dis[v][v2] ) continue ; 
            dis[v][v2] = dis[v2][v] = 1, q.push((Node){ v, v2 }) ;  
        }
    }
}

然后是,看不懂的部分了 QAQ (研究了半天题解都看不懂.jpg)

注意到边数很多,然而点数较少,能不能在这上面优化?

首先只考虑连接了两个相同颜色$(0/1)$的点的边,这样的边会将原图构成若干个联通块。

对每个联通块单独考虑,如果这个联通块是二分图,那么我们可以将点分成两类$1,2$,不难发现从$1$类走到$2$类总是要经过奇数条边,而从某一类走回某一类还是会经过偶数条边,(假设点均为 $1$ ),也就是途中会得到偶数/奇数个 $1$

然而实际上对于这个二分图只保留其生成树仍然具有这个性质。因为题目中说允许重复经过某一个点。所以我们在这个二分图中反复走环等其实经过的点数的奇偶性仍然相同。这与在其生成树上重复经过同一条边是等价的。

对于一个回文串 $000111000$ 其可以看作先后经过了三个联通块(先假设这些联通块都是二分图)

不难发现对于每个联通块内部经过的奇偶数量是一样的。类似的去画下图,可以发现只保留生成树是不会对答案造成影响。

如果这个图不是二分图呢?我们发现对于不是二分图的图我们总可以通过不断地绕圈得到奇/偶的点对,所以我们需要在其生成树上加上一个自环。

对于连接了$0$和$1$的边也类似讨论,这些边组成的图显然是一个二分图(0一类,1一类)我们对其也只需要保留一颗生成树。

然后这样做的话最后总边数:$(m->n)$

复杂度据说是$O(N^2)???$

#include<bits/stdc++.h>
using namespace std;
int read() {
    char cc = getchar(); int cn = 0;
    while(cc < '0' || cc > '9') cc = getchar();
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn;
}
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i ) 
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next ) 
const int M = 1e6 + 5 ; 
const int N = 5000 + 5;
struct E {
    int to, next ;  
} e[M * 2];
struct S {
    int from, to ; 
} s[M * 2];
int n, m, Q, head[N], cnt, w[N], dis[N][N], fa[N][2], col[N], sd[N], book[N];
char ss[N] ; 
queue< S> q ;  
void add( int x, int y ) {
    e[++ cnt] = (E){ y, head[x] }, head[x] = cnt ; 
    e[++ cnt] = (E){ x, head[y] }, head[y] = cnt ; 
}
int abc( int x ) { //绝对值 
    return ( x > 0 ) ? x : -x ; 
}
int find( int x, int node ) {
    if( fa[x][node] == x ) return x ; 
    return fa[x][node] = find(fa[x][node], node) ; 
}
void dfs( int x, int c ) {
    col[x] = c ; 
    Next( i, x ) {
        int v = e[i].to ; 
        if( !col[v] ) dfs( v, -c ) ;
        else if( col[v] == col[x] ) sd[abc(c)] = 1 ; 
    }
}
void init() {
    rep( i, 1, n ) if( !col[i] ) dfs( i, i ) ;  //二分图染色 

    memset( head, 0, sizeof(head) ), cnt = 0 ;
    rep( i, 1, m ) {
        int Fr = s[i].from, To = s[i].to ; 
        if( w[Fr] != w[To] ) {
            int u = find( Fr, 1 ), v = find( To, 1 ) ;
            if( u == v ) continue ;
            add( Fr, To ), fa[u][1] = v ;
        }
        else {
            int u = find(Fr, 0), v = find(To, 0) ; 
            if( u == v ) continue ; 
            add( Fr, To ), fa[u][0] = v ; 
            q.push((S){ Fr, To }), dis[Fr][To] = dis[To][Fr] = 1 ; 
        } 
    }
    rep( i, 1, n ) {
        int cc = abc(col[i]) ;
        if( sd[cc] && ( book[cc] == 0 ) ) add( cc, cc ), book[cc] = 1 ; //自环 
    }
}
void spfa() { //spfa求解两个点是否可达 
    while( !q.empty() ) {
        S u = q.front(); q.pop() ;
        int Fr = u.from, To = u.to ; 
        Next( i, Fr ) {
            int v = e[i].to ; 
            Next( j, To ) {
                int v2 = e[j].to ; 
                if( w[v] != w[v2] || dis[v][v2] ) continue ; 
                dis[v][v2] = dis[v2][v] = 1, q.push((S){v, v2}) ;
            }
        } 
    }
}
void output() { //输出文件 
    int x, y ; 
    rep( i, 1, Q ) {
        x = read(), y = read() ; 
        if( dis[x][y] ) puts("YES") ; 
        else puts("NO") ; 
    }
}
signed main()
{
    n = read(), m = read(), Q = read() ; 
    scanf("%s", ss);
    rep( i, 1, n ) w[i] = ss[i - 1] - '0', dis[i][i] = 1, fa[i][0] = fa[i][1] = i, q.push((S){i, i}) ;
    rep( i, 1, m ) {
        s[i].from = read(), s[i].to = read();
        if( w[s[i].from] == w[s[i].to] ) add( s[i].from, s[i].to ) ;
    }
    init(), spfa(), output() ; 
    return 0;
}

评论

  • yzhang
    orz
作者: yybyyb 更新时间: 2019-04-08 16:26  在Ta的博客查看    4  

首先考虑暴力做法怎么做。
把所有可行的二元组全部丢进队列里,每次两个点分别向两侧拓展一个同色点,然后更新可行的情况。
这样子的复杂度是$O(m^2)$的。
考虑如何优化边数,先说结论:
首先对于一个同色联通块,如果它是一个二分图,那么只需要保留一棵生成树就行了,否则随便找个点连一条自环。
对于连接不同色两个点的边,一定构成一个二分图,只需要保留一棵生成树就行了。
证明是这样子的:
首先我们把路径划分成若干个同色连续段,那么我们要做的就是对应的两段长度要相等。
长度短了是无所谓的,我们可以反复走一条边,达到把序列边长的目的。
对于一个二分图而言,如果反复走,其长度的奇偶性不会改变,否则奇偶性可以任意改变,那么需要连一个自环来改变奇偶性。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define MAX 5050
inline int read()
{
    int x=0;char ch=getchar();bool fl=false;
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')fl=true,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return fl?-x:x;
}
struct Line{int v,next;}e[500500<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int n,m,Qr;char a[MAX];
struct Node{int x,y;};queue<Node> Q;
bool vis[MAX][MAX];
vector<int> E[MAX];
int col[MAX];bool chk;
int f[MAX];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
void dfs(int u,int c)
{
    col[u]=c;
    for(int i=0,l=E[u].size();i<l;++i)
    {
        int v=E[u][i];
        if(a[u]!=a[v])continue;
        if(col[v]==col[u])chk=false;
        if(col[v])continue;
        Add(u,v),Add(v,u);dfs(v,c^1);
        vis[u][v]=vis[v][u]=true;
        Q.push((Node){u,v});
    }
}
int main()
{
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    n=read();m=read();Qr=read();scanf("%s",a+1);
    for(int i=1;i<=n;++i)f[i]=i;
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        E[u].push_back(v);
        E[v].push_back(u);
        if(a[u]!=a[v])
        {
            if(getf(u)==getf(v))continue;
            Add(u,v);Add(v,u);
            f[getf(u)]=getf(v);
        }
    }
    for(int i=1;i<=n;++i)
        if(!col[i])
        {
            chk=true;dfs(i,2);
            if(!chk)Add(i,i);
        }
    for(int i=1;i<=n;++i)vis[i][i]=true,Q.push((Node){i,i});
    while(!Q.empty())
    {
        Node u=Q.front();Q.pop();
        int x=u.x,y=u.y;
        for(int i=h[x];i;i=e[i].next)
        {
            int xx=e[i].v;
            for(int j=h[y];j;j=e[j].next)
            {
                int yy=e[j].v;
                if(vis[xx][yy])continue;
                if(a[xx]!=a[yy])continue;
                vis[xx][yy]=vis[yy][xx]=true;
                Q.push((Node){xx,yy});
            }
        }
    }
    while(Qr--)
    {
        int x=read(),y=read();
        if(vis[x][y])puts("YES");
        else puts("NO");
    }
    return 0;
}

评论

  • 还没有评论
作者: 洛水·锦依卫 更新时间: 2019-04-09 20:55  在Ta的博客查看    2  

欢迎来博客玩呀

Algorithm

$DP$

Mentality

考场上无人切的神题 $orz$ ,$myy\ nb$ 。

由于 $n$ 异常的小,所以我们发现完全可以用 $n^2$ 的二维空间来储存信息,而 $m$ 和 $q$ 相对来说又异常大,这启发我们用一种看起来很暴力的方法做这道题 -- 预处理出所有点对的情况。

$30$ 分的做法还是很好想的,我们发现可以将回文路径分为两类:长度为奇数的,长度为偶数的。

设 $f[i][j]$ 为 $i,j$ 之间是否有回文路径,那么我们先处理出长度最短的奇偶回文路径。首先,长度最短的奇数回文路径就是每个点自己,即 $f[i][i]=1$ 。然后观察到对于每条边,如果连的两个点 $u,v$ 编号相同,则 $f[u][v]=f[v][u]=1$ ,这些就是长度最短的偶数回文路径。

然后考虑利用这些信息进行 $DP$ 转移,我们用 $bfs$ 的顺序来转移即可。

将这些两点之间有路径的二元组 $(u,v)$ 扔进队列,转移的时候枚举 $u,v$ 的出边 $to_u,to_v$,如果 $to_u$ 的编号与 $to_v$ 相同,那么 $to_u,to_v$ 之间肯定也存在回文路径,我们将 $f$ 数组更新,然后将二元组 $to_u,to_v$ 丢入队列末尾等待下一次转移即可。

由于每次转移都要枚举两点的出边一一判断,所以复杂度为 $m^2$ 。

代码大概长这个样子?

while(h<t)
{
    h++;
    for(int i=hd[u[h]];i;i=Nx[i])
        for(int j=hd[v[h]];j;j=Nx[j])
            if(S[To[i]]==S[To[j]]&&!f[To[i]][To[j]])
                f[To[i]][To[j]]=f[To[j]][To[i]]=1,Add(To[i],To[j]);
}

由于 $STL$ 常数太大,所以手写队列 (也就总共 $5e7$ 的空间而已)

询问一次就直接看它的 $f$ 数组即可。

接下来考虑 $100$ 分做法。

观察到 $m$ 巨大,我们考虑减少边的枚举。

我们将所有转移分成两类:向相同编号的点转移,向不同编号的点转移。

那么我们也就可以依此将边分为两类:连接相同编号点的边,连接不同编号点的边。

我们先考虑一类边,譬如连接相同编号点的边。

这些边把图分成了许多个联通块,我们发现,对于一个联通块内的转移,只取决于一件事:这个联通块是不是个二分图。

为什么呢?我们来考虑一下,如果联通块是一个二分图,那么它满足两个性质。

  • 能将联通块内的点划分成两个集合,同一集合内的点互不直接相连。

  • 同时由于这是个联通块,两点之间皆可达。

那么不难发现,如果我在一个集合内,想要转移到集合内另一点,必定会经过偶数条边。

因为我到达这个点的过程中,注定只能是重复 当前集合 -> 另一集合 -> 当前集合 这样的步骤,所以最后的步数一定是偶数条。

换而言之,若联通块为二分图,那么联通块内任意两点之间的路径长度奇偶性唯一。

而注意到,当我们 $DP$ 转移的时候,若回文串两端新增的数字全都相同,譬如在左右端都添上 $0$ ,那么我们只需要保证左右两边新增的数量相同即可。

而根据题目的性质可知,我们为保证数量相等,完全可以在一条连向一个相同编号点的边上来回横走保证数量的增值。但是这样不改变奇偶性

那么奇偶性就成了判断 $DP$ 转移的重要性质了。

接着上面的推论,由于若联通块为二分图,那么联通块内两点件路径长度奇偶性唯一。那么我们在这个联通块内,只需要保留一颗生成树即可,因为 奇偶唯一 ,所以 不影响 $DP$ 过程

然后我们再来看,如果不是二分图怎么办。还是划分成两个集合,那么同一集合内至少有一对点 $(u,v)$ 之间直接有连边。由于只考虑连接两个不同集合的边时,从 $u$ 至 $v$ 必定有一条长度为 偶数 的路径,所以再加上一条边,这个联通块内就有了一个 奇环 。则联通块内任意一点都可以走到奇环上通过绕环改变路径长度奇偶性。

那么不难发现,我们只需要先像二分图一样,保留一颗生成树。至于那个奇环,我们只需要在生成树内任意一个点上随便连个自环就行了 $QwQ$,反正只是要个奇环而已,自环当然也是啦。

以上是连接相同编号点的边的处理方式。

至于连接不同编号的边的话,我们发现这联通块肯定就是个二分图,那么直接保留生成树即可。

那么边数减少为 $n$ 的级别,此时再去 $DP$ ,复杂度就降为 $n^2$ 了。

如若未懂详见代码

Code

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,Q;
int cntr,head[5001],nx[1000001],to[1000001],col[5001];
int cr,hd[5001],Nx[1000001],To[1000001];
int h,t,u[25000001],v[25000001];
bool flag,f[5001][5001];
char S[5001];
struct node{int u,v;};
void read(int &x)
{
    x=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
}
void addr(int u,int v)
{
    cntr++;
    nx[cntr]=head[u],to[cntr]=v;
    head[u]=cntr;
}
void Addr(int u,int v)
{
    cr++;
    Nx[cr]=hd[u],To[cr]=v;
    hd[u]=cr;
}
void Add(int U,int V)
{
    t++;
    u[t]=U,v[t]=V;
}
void dye(int x,bool type)
{
    for(int i=head[x];i;i=nx[i])
    {
        int p=to[i];
        if((S[p]==S[x])==type)//构图参数的使用
        {
            if(col[p]!=-1)if(!(col[p]^col[x]))flag=1;//染色冲突则不是二分图
            if(col[p]==-1)
            {
                col[p]=col[x]^1,dye(p,type);
                Addr(x,p),Addr(p,x);//加边
            }
        }
    }
}
void Read_Init()
{
    read(n),read(m),read(Q);
    scanf("%s",S+1);
    int u,v;
    while(m--)
    {
        read(u),read(v);
        if(S[u]==S[v])f[u][v]=f[v][u]=1,Add(u,v);//先加入偶数最短边,并更新 DP 数组
        addr(u,v),addr(v,u);
    }
}
void Build_Init()
{
    for(int i=1;i<=n;i++)f[i][i]=1,Add(i,i);//加入奇数最短边,并更新 DP 数组
    for(int k=0;k<2;k++)//k 是构图参数
    {
        for(int i=1;i<=n;i++)col[i]=-1;//二分图染色初始化
        for(int i=1;i<=n;i++)
            if(col[i]==-1)
            {
                flag=0;
                col[i]=0,dye(i,k);
                if(flag)Addr(i,i);//如果不是二分图那就加个自环
            }
    }
}
void DP()
{
    while(h<t)
    {
        h++;
        for(int i=hd[u[h]];i;i=Nx[i])
            for(int j=hd[v[h]];j;j=Nx[j])
                if(S[To[i]]==S[To[j]]&&!f[To[i]][To[j]])
                    f[To[i]][To[j]]=f[To[j]][To[i]]=1,Add(To[i],To[j]);//DP 转移
    }
}
void Answer()
{
    int u,v;
    while(Q--)
    {
        read(u),read(v);
        if(f[u][v])printf("YES\n");
        else printf("NO\n");
    }
}
int main()
{
    Read_Init();
    Build_Init();
    DP();
    Answer();
}

评论

  • 还没有评论
作者: TheLostWeak 更新时间: 2019-04-18 20:07  在Ta的博客查看    1  

在博客查看

大致题意: 给你一张无向图,每个点权值为$0$或$1$,多组询问两点之间是否存在一条回文路径。

暴力$DP$

首先,看到$n$如此之小($n\le5000$),便容易想到一个$O(m^2)$的暴力$DP$。

我们用$f_{i,j}$表示$i$与$j$两点之间是否存在一条回文路径

初始化,$f_{i,i}=1,f_{i,j}=1(s_i=s_j)$,即分别预处理最短的奇数长度回文路径和偶数长度回文路径。

然后我们把所有$f_{i,j}=1$的点对$(i,j)$扔入一个队列里,用类似于$BFS$的方式,每次枚举$i$的一个相邻节点$x$与$j$的一个相邻节点$y$,如果$s_x=s_y$,则显然存在一条回文路径$x->i->j->y$,因此更新$f_{x,y}=1$并将$(x,y)$扔入队列里。

这里要加上一个很显然的优化,即如果$f_{x,y}$原本就为$1$,我们就不进行操作。

这样每组点对最多被枚举一次,这里的时间复杂度是$O(n^2)$。

但枚举相邻节点时要同时枚举两条边,因此复杂度就变成了$O(m^2)$。

不难发现,这个算法时间复杂度的瓶颈就在于枚举两条边这里,因此我们需要考虑对这个地方进行优化。

奇偶性与二分图性质

我们先考虑只在同色点之间连边

考虑到每条边可以重复多次,也就是说,我们在转移时如果在一条边上无限走,则可以无限刷长度。

但是,我们无限刷长度不一定能改变奇偶性

不过,我们至少可以得出一个结论,在$DP$转移时,只要是奇偶性相同的一段同色路径,我们就可以进行转移。

那么什么时候奇偶性不同也可以转移呢?

这时候就要借助二分图的定义来求解了。

考虑先判断当前图是否是二分图,这只需要$DFS$给相邻点染不同颜色,出现矛盾就说明不是二分图,否则是二分图。

而二分图有个性质,即可以将图中点集划分成两部分,其中同一部分的点之间没有边。

也就是说,从一个点出发,必然要沿着这一个点集$->$另一个点集$->$这一个点集$->$另一个点集$->...->$这一个点集这样的路径走才能走回到该点,则经过边数为偶数,无法改变奇偶性。

否则,图中必然存在奇环,而通过奇环就可以改变奇偶性了。

大力删边

所以我们前面讲了这么多是要干什么呢?就是为了删掉图中的一些边,使边数变成$O(n)$规模。

我们要明白二分图的另一个性质,即二分图的一棵生成树也满足二分图性质,无法改变奇偶性。

因此,对于每一个是二分图的同色连通块,我们就可以只保留一棵生成树。

而对于不是二分图的连通块,其实我们也可以先取一棵生成树,然后只要给这张图中任意一个节点加上一个自环,这样也可以改变奇偶性,与原连通块是等价的。

而对于只在异色点之间连边,也有类似的规律,而且我们可以发现它必定是二分图(将点集按颜色划分成两个点集),可以直接保留生成树。

于是点一下就少了很多,可以直接按前面的暴力$DP$来搞了!

这时边数是$O(n)$,所以时间复杂度也就是$O(n^2)$。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 5000
#define M 500000
#define mp make_pair
#define fir first
#define sec second
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,ee,H,T,lnk[N+5],f[N+5][N+5];string s;
struct edge {int to,nxt;}e[(M<<1)+5];
typedef pair<int,int> Pr;Pr q[N*N+5];
class FastIO
{
    private:
        #define FS 100000
        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
        #define tn (x<<3)+(x<<1)
        #define D isdigit(c=tc())
        char c,*A,*B,FI[FS];
    public:
        I FastIO() {A=B=FI;}
        Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
        I void reads(string& x) {x="";W(isspace(c=tc()));W(x+=c,!isspace(c=tc())&&~c);}
}F;
class GraphBuilder//建新图
{
    private:
        #define nadd(x,y) (ne[++nee].nxt=nlnk[x],ne[nlnk[x]=nee].to=y)//建新边
        int nee,t,col[N+5];
        I void Travel(CI x,CI op)//扫一遍连通块(op表示只能在同色/异色点间连边),建好生成树,同时判断是否为二分图
        {
            for(RI i=lnk[x];i;i=e[i].nxt) (s[x-1]==s[e[i].to-1])==op&&
            (
                col[e[i].to]?(col[x]==col[e[i].to]&&(t=0))//如果产生矛盾说明不是二分图
                :(col[e[i].to]=3-col[x],Travel(e[i].to,op),nadd(x,e[i].to),nadd(e[i].to,x))//给相邻点染上不同颜色
            );
        }
    public:
        int nlnk[N+5];edge ne[(M<<1)+5];
        I void Build()//建图
        {
            #define Clear() for(i=1;i<=n;++i) col[i]=0
            RI i;Clear();for(i=1;i<=n;++i) !col[i]&&(col[i]=t=1,Travel(i,1),!t&&nadd(i,i));//对于非二分图建一个自环
            Clear();for(i=1;i<=n;++i) !col[i]&&(col[i]=1,Travel(i,0),0);
        }
}G;
#define Push(x,y) (q[++T]=mp(x,y),f[x][y]=f[y][x]=1)
I void DP()//动态规划
{
    RI i,j;Pr k;W(H<=T) for(i=G.nlnk[(k=q[H++]).fir];i;i=G.ne[i].nxt)//枚第一个点的相邻节点
        for(j=G.nlnk[k.sec];j;j=G.ne[j].nxt) s[G.ne[i].to-1]==s[G.ne[j].to-1]&&//枚第二个点的相邻节点
            !f[G.ne[i].to][G.ne[j].to]&&Push(G.ne[i].to,G.ne[j].to);//扔入队列中
}
int main()
{
    RI Qtot,i,x,y;for(F.read(n,m,Qtot),F.reads(s),i=1;i<=m;++i)//读入数据
        F.read(x,y),add(x,y),add(y,x),s[x-1]==s[y-1]&&Push(x,y);//初始化队列
    for(G.Build(),i=1;i<=n;++i) Push(i,i);DP();//建新图,初始化队列,然后DP
    W(Qtot--) F.read(x,y),puts(f[x][y]?"YES":"NO");return 0;//对于每个询问输出答案
}

评论

  • 还没有评论
作者: Imakf 更新时间: 2019-04-08 17:50  在Ta的博客查看    1  

神仙dp题,考场爆0只有我了

解法

myy出的,搬一下他的原话如下

30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径,转移就是枚举i的边和j的边。总复杂度是$O(m^2)$。

考虑减少边数。我们把一种标号单独拿出来,只考虑连接同一种标号的两个点的边。 对于一个连通块,如果它是二分图,那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现(只要另一边在两个点内来回走即可)。如果它不是二分图,我们可以加一个自环。

我们考虑连接不同标号的边,只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块, 根据同样的道理我们保留一棵生成树即可(注意这个时候连通块一定都是二分图)。

这样总边数不超过$2n-2$,用30分DP的思路可以做到$O(n^2)$并且通过本题。


所以为什么不是二分图的时候可以加自环呢?仔细想想,如果图不是二分图,就说明图中一定有长度为奇数的环。那么在这边可以一直来回转圈,另一边如果也有奇数环,那么显然可以匹配,如果另一边是二分图,那么显然我们可以在这一边转上几圈,让长度变成偶数,依然可以转移QAQ

如果不懂的话可以自己手造数据的QAQ,个人认为比较好理解

于是就变成了$kruskal$

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>

#define rg register
#define il inline
#define MX (5000 + 65)
#define M_MX (500000 + 5)

int cs ,cd;
struct ip{
    int u ,v;
}same[M_MX] ,diff[M_MX];
int color[MX];

namespace FS{   //forward_star 前向星
    int head[MX] ,tot;
    struct edge{
        int node ,next;
    }h[M_MX << 1];
    il void addedge(int u ,int v){
        h[++tot].next = head[u];
        head[u] = tot;
        h[tot].node = v;
    }
}
int n ,m ,q;

int fa[MX];
void init(int upper){
    for(rg int i = 1 ; i <= upper ; ++i)    fa[i] = i;
    using namespace FS;
    memset(FS::head ,0 ,sizeof(head));
    memset(h ,0 ,sizeof(h));
    tot = 0;
}
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void link(int x ,int y){fa[find(x)] = find(y);}

int vis[MX][MX] ,DP[MX][MX];
namespace MST{  //Minimum Spanning Tree 最小生成树
    int head[MX] ,tot;
    FS::edge h[M_MX << 1];
    void addedge(int u ,int v){
        h[++tot].next = head[u];
        head[u] = tot;
        h[tot].node = v;
    }int Tag[MX];
    bool check2fen(int x ,int tag){
        if(Tag[x])  return Tag[x] == tag;
        Tag[x] = tag;
        for(rg int i = FS::head[x] ; i ; i = FS::h[i].next){
            int d = FS::h[i].node;
            if(!check2fen(d ,tag == 1 ? 2 : 1)) return false;
        }return true;
    }
    void kruskal(int type){
        if(type == 1){  //单独拿出连接同种编号的
            for(rg int i = 1 ; i <= n ; ++i)    Tag[i] = false;
            init(n);
            int cnt = 0;
            for(rg int i = 1 ; i <= cs ; ++i){
                FS::addedge(same[i].u ,same[i].v);
                FS::addedge(same[i].v ,same[i].u);
            }
            for(rg int i = 1 ; i <= cs ; ++i){
                if(find(same[i].u) != find(same[i].v)){
                    LST::addedge(same[i].u ,same[i].v);
                    LST::addedge(same[i].v ,same[i].u);
                    link(same[i].u ,same[i].v);
                    ++cnt;
                }
            }
            for(rg int i = 1 ; i <= n ; ++i){
                if(!Tag[i]){
                    if(!check2fen(i ,1))    LST::addedge(i ,i);
                }
            }
        }
        else{//单独拿出连接不同种编号的
            init(n);
            for(rg int i = 1 ; i <= n ; ++i)    Tag[i] = false;
            int cnt = 0;
            for(rg int i = 1 ; i <= cd ; ++i){
                FS::addedge(diff[i].u ,diff[i].v);
                FS::addedge(diff[i].v ,diff[i].u);
            }
            for(rg int i = 1 ; i <= cd ; ++i){
                if(find(diff[i].u) != find(diff[i].v)){
                    LST::addedge(diff[i].u ,diff[i].v);
                    LST::addedge(diff[i].v ,diff[i].u);
                    link(diff[i].u ,diff[i].v);
                    ++cnt;
                }
            }
            for(rg int i = 1 ; i <= n ; ++i){
                if(!Tag[i]){
                    if(!check2fen(i ,1))    LST::addedge(i ,i);
                }
            }
        }
    }
}using namespace MST;

void dp(){  //大力转移,因为本题有O2,可以放心用STL
    std::queue<int> q1 ,q2;
    for(rg int i = 1 ; i <= n ; ++i){
        vis[i][i] = true;
        DP[i][i] = true;
        q1.push(i) ,q2.push(i);
        for(rg int j = head[i] ,d ; j ; j = h[j].next){
            d = h[j].node;
            vis[i][d] = vis[d][i] = true;
            if(color[i] != color[d])    continue;
            DP[i][d] = DP[d][i] = true;
            q1.push(i) ,q2.push(d);
        }
    }
    while(!q1.empty()){
        int x = q1.front() ,y = q2.front();
        q1.pop() ,q2.pop();
        for(rg int i = head[x] ; i ; i = h[i].next){
            for(rg int j = head[y] ; j ; j = h[j].next){
                if(!vis[h[i].node][h[j].node] && color[h[i].node] == color[h[j].node]){
                    DP[h[i].node][h[j].node] = DP[h[j].node][h[i].node] = true;
                    q1.push(h[i].node) ,q2.push(h[j].node);
                }vis[h[i].node][h[j].node] = vis[h[j].node][h[i].node] = true;
            }
        }
    }
}

int main(){

    scanf("%d%d%d" ,&n ,&m ,&q);
    for(rg int i = 1 ; i <= n ; ++i){
        scanf("%1d" ,color + i);
    }
    for(rg int i = 1 ,u ,v ; i <= m ; ++i){
        scanf("%d%d" ,&u ,&v);
        FS::addedge(u ,v);
        FS::addedge(v ,u);
        if(color[u] ^ color[v]) diff[++cd] = (ip){u ,v};
        else same[++cs] = (ip){u ,v};
    }
    using namespace MST;
    kruskal(1);
    kruskal(2);
    //outedge();
    dp();
    for(rg int i = 1 ,u ,v ; i <= q ; ++i){
        scanf("%d%d" ,&u ,&v);
        if(DP[u][v] || DP[v][u])    puts("YES");
        else puts("NO");
    }
    return 0;
}