【HYSBZOJ】【搜索】[Hnoi2019]校园旅行_综合

HYSBZOJ 5492 [Hnoi2019]校园旅行

题目大意

◇题目传送门◆

分析

首先我们不难发现，一个回文串去掉首尾之后一定是一个回文串。

所以我们可以根据这个性质来做：

假设 $(x, y)$ 是一对可以通过回文串相互到达的点对，那么我们可以枚举 $x$ 的邻接点 $u$ ， $y$ 的邻接点 $v$ ，当 $u, v$ 同色时，它们就可以通过回文串相互到达。然后我们按照 BFS 顺序转移即可。

这样做我们需要枚举所有的边，复杂度为 $O(M^2)$ 的，显然过不了这题。

代码就不给了吧。。。

考虑如何减少边数。

考虑将连接相同颜色的边拿出来，这样原图就被划分成若干个连通块。

这样的话如果某个连通块是二分图，那么我们从 $X$ 部走到 $Y$ 部会经过恰好奇数条边，而从 $X$ 部走回 $X$ 部或者从 $Y$ 部走回 $Y$ 部会经过恰好偶数条边。也就是说，我们恰好会得到奇数/偶数个 $0$ 或者 $1$ 。

实际上，我们对于这个连通块，保留它的一棵生成树就够了。因为题目中没有要求只走简单路径，所以在原来的二分图上走环就可以转化成在生成树上走重复的边了。这样只留下一棵生成树的话对于答案是没有影响的。

但当这个连通块不是二分图的时候，我们可以发现通过不断地绕着环走可以改变长度奇偶性，所以我们在这个图上的生成树上随便加一个自环就可以了。

对于连着不同颜色的边也做同样的处理，不难发现这时它一定是一个二分图。

这样的话边数最多不会超过 $2 N ? 2$ 了。

我们在建好的新图上用暴力的方法跑就可以了，复杂度为 $O(N^2)$ 。

注意这道题输入数据很大，要写个读入优化才能过。

参考代码

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 5000;
const int Maxm = 500000;struct DSU {
    int fa[Maxn + 5];void init(int n) {
    for(int i = 1; i <= n; i++)fa[i] = i;}int find(int u) {
    return u == fa[u] ? u : fa[u] = find(fa[u]);}void unite(int u, int v) {
    u = find(u), v = find(v);if(u == v) return;fa[u] = v;}bool same(int u, int v) {
    return find(u) == find(v);}
};int N, M;
char tag[Maxn + 5];
bool f[Maxn + 5][Maxn + 5];DSU s;vector<int> G[Maxn + 5];
void addedge(int u, int v) {
    G[u].push_back(v), G[v].push_back(u);
}vector<int> G1[Maxn + 5];
void addedge1(int u, int v) {
    if(u == v) G1[u].push_back(v);else G1[u].push_back(v), G1[v].push_back(u);
}queue<pair<int, int> > q;
int col[Maxn + 5];
bool has_odd;
void DFS(int u, int c) {
    col[u] = c;for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];if(tag[u] != tag[v]) continue;if(col[u] == col[v]) has_odd = true;if(col[v]) continue;addedge1(u, v);DFS(v, c ^ 1);f[u][v] = f[v][u] = true;q.push(make_pair(u, v));}
}
void rebuild() {
    for(int i = 1; i <= N; i++)if(!col[i]) {
    has_odd = false;DFS(i, 2);if(has_odd) addedge1(i, i);}
}void BFS() {
    while(!q.empty()) {
    int u = q.front().first, v = q.front().second;q.pop();for(int i = 0; i < (int)G1[u].size(); i++)for(int j = 0; j < (int)G1[v].size(); j++) {
    int tu = G1[u][i], tv = G1[v][j];if(f[tu][tv]) continue;if(tag[tu] != tag[tv]) continue;f[tu][tv] = f[tv][tu] = true;q.push(make_pair(tu, tv));}}
}inline int read() {
    char ch = getchar();int ret = 0;bool w = false;while(ch > '9' || ch < '0') {
    if(ch == '-') w = true;ch = getchar();}while(ch >= '0' && ch <= '9') {
    ret = ret * 10 + (ch ^ 48);ch = getchar();}return w ? -ret : ret;
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifN = read(), M = read();int Q = read();scanf("%s", tag + 1);s.init(N);for(int i = 1; i <= M; i++) {
    int u = read(), v = read();addedge(u, v);if(tag[u] != tag[v]) {
    if(s.same(u, v)) continue;addedge1(u, v);s.unite(u, v);}}rebuild();for(int i = 1; i <= N; i++)f[i][i] = true, q.push(make_pair(i, i));BFS();while(Q--) {
    int u = read(), v = read();puts(f[u][v] ? "YES" : "NO");}return 0;
}