题解 P5292 【[HNOI2019]校园旅行】

[在博客查看](https://www.cnblogs.com/chenxiaoran666/p/Luogu5292.html ) **大致题意：** 给你一张无向图，每个点权值为$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)$。 ### 代码 ```cpp #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;//对于每个询问输出答案 } ```