题解 P5292 【[HNOI2019]校园旅行】
Soulist
2019-04-08 19:37:27
神仙题,之前写过一篇题解,可能较为难懂,最近订正一下
首先注意到一个回文串将其首尾去除仍为回文串。
于是可以类似于 spfa 从长度为 $2/1$ 的回文串开始遍历,求出任意两点是否回文可达,这样每一对点都会拓展一次,复杂度为 $deg\times deg$,即 $\mathcal O((\sum deg)^2)=\mathcal O(m^2)$
我们注意到,一个回文串可以被描述为若干段 $01$ 和 $11$ 和 $00$ 的组合,而且由于允许走非简单路径,那么重复绕同一边走可以改变任意一段的奇偶性,于是答案只和每一段的奇偶性相关。
考虑什么图中某两个点的奇偶性恒定 $\to$ 二分图,于是将 $01$ 边单独考虑,$1\to 1$ 边单独考虑,$0\to 0$ 边单独考虑,如果为二分图,那么只需要保留任意一棵生成树即可保证答案相同(注意这仍是一个二分图,同时绕重边任何合法)若为非二分图,我们增加一个自环即可(可以通过绕自环来改变某两个点奇偶性)。
这样可以将边数降为 $n$ 的级别,然后做上面那个暴力,复杂度即为 $\mathcal O(n^2)$
```cpp
#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;
}
```