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

Soulist

2019-04-08 19:37:27

Solution

神仙题,之前写过一篇题解,可能较为难懂,最近订正一下 首先注意到一个回文串将其首尾去除仍为回文串。 于是可以类似于 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; } ```