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