【BZOJ5492】[HNOI2019]校园旅行（bfs）

[HNOI2019]校园旅行（bfs）

题面

洛谷

题解

首先考虑暴力做法怎么做。

把所有可行的二元组全部丢进队列里，每次两个点分别向两侧拓展一个同色点，然后更新可行的情况。

这样子的复杂度是\(O(m^2)\)的。

考虑如何优化边数，先说结论：

首先对于一个同色联通块，如果它是一个二分图，那么只需要保留一棵生成树就行了，否则随便找个点连一条自环。

对于连接不同色两个点的边，一定构成一个二分图，只需要保留一棵生成树就行了。

证明是这样子的：

首先我们把路径划分成若干个同色连续段，那么我们要做的就是对应的两段长度要相等。

长度短了是无所谓的，我们可以反复走一条边，达到把序列边长的目的。

对于一个二分图而言，如果反复走，其长度的奇偶性不会改变，否则奇偶性可以任意改变，那么需要连一个自环来改变奇偶性。

#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;

}