自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:09:10，当前版本为作者最后更新于2019-04-08 17:50:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神仙dp题，考场爆0只有我了

解法

myy出的，搬一下他的原话如下

30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径，转移就是枚举i的边和j的边。总复杂度是$O(m^2)$。

考虑减少边数。我们把一种标号单独拿出来，只考虑连接同一种标号的两个点的边。 对于一个连通块，如果它是二分图，那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现（只要另一边在两个点内来回走即可）。如果它不是二分图，我们可以加一个自环。

我们考虑连接不同标号的边，只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块， 根据同样的道理我们保留一棵生成树即可（注意这个时候连通块一定都是二分图）。

这样总边数不超过$2n-2$，用30分DP的思路可以做到$O(n^2)$并且通过本题。

所以为什么不是二分图的时候可以加自环呢？仔细想想，如果图不是二分图，就说明图中一定有长度为奇数的环。那么在这边可以一直来回转圈，另一边如果也有奇数环，那么显然可以匹配，如果另一边是二分图，那么显然我们可以在这一边转上几圈，让长度变成偶数，依然可以转移QAQ

如果不懂的话可以自己手造数据的QAQ，个人认为比较好理解

于是就变成了$kruskal$

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>

#define rg register
#define il inline
#define MX (5000 + 65)
#define M_MX (500000 + 5)

int cs ,cd;
struct ip{
	int u ,v;
}same[M_MX] ,diff[M_MX];
int color[MX];

namespace FS{	//forward_star 前向星
	int head[MX] ,tot;
	struct edge{
		int node ,next;
	}h[M_MX << 1];
	il void addedge(int u ,int v){
		h[++tot].next = head[u];
		head[u] = tot;
		h[tot].node = v;
	}
}
int n ,m ,q;

int fa[MX];
void init(int upper){
	for(rg int i = 1 ; i <= upper ; ++i)	fa[i] = i;
	using namespace FS;
	memset(FS::head ,0 ,sizeof(head));
	memset(h ,0 ,sizeof(h));
	tot = 0;
}
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void link(int x ,int y){fa[find(x)] = find(y);}

int vis[MX][MX] ,DP[MX][MX];
namespace MST{	//Minimum Spanning Tree 最小生成树
	int head[MX] ,tot;
	FS::edge h[M_MX << 1];
	void addedge(int u ,int v){
		h[++tot].next = head[u];
		head[u] = tot;
		h[tot].node = v;
	}int Tag[MX];
	bool check2fen(int x ,int tag){
		if(Tag[x])	return Tag[x] == tag;
		Tag[x] = tag;
		for(rg int i = FS::head[x] ; i ; i = FS::h[i].next){
			int d = FS::h[i].node;
			if(!check2fen(d ,tag == 1 ? 2 : 1))	return false;
		}return true;
	}
	void kruskal(int type){
		if(type == 1){	//单独拿出连接同种编号的
			for(rg int i = 1 ; i <= n ; ++i)	Tag[i] = false;
			init(n);
			int cnt = 0;
			for(rg int i = 1 ; i <= cs ; ++i){
				FS::addedge(same[i].u ,same[i].v);
				FS::addedge(same[i].v ,same[i].u);
			}
			for(rg int i = 1 ; i <= cs ; ++i){
				if(find(same[i].u) != find(same[i].v)){
					LST::addedge(same[i].u ,same[i].v);
					LST::addedge(same[i].v ,same[i].u);
					link(same[i].u ,same[i].v);
					++cnt;
				}
			}
			for(rg int i = 1 ; i <= n ; ++i){
				if(!Tag[i]){
					if(!check2fen(i ,1))	LST::addedge(i ,i);
				}
			}
		}
		else{//单独拿出连接不同种编号的
			init(n);
			for(rg int i = 1 ; i <= n ; ++i)	Tag[i] = false;
			int cnt = 0;
			for(rg int i = 1 ; i <= cd ; ++i){
				FS::addedge(diff[i].u ,diff[i].v);
				FS::addedge(diff[i].v ,diff[i].u);
			}
			for(rg int i = 1 ; i <= cd ; ++i){
				if(find(diff[i].u) != find(diff[i].v)){
					LST::addedge(diff[i].u ,diff[i].v);
					LST::addedge(diff[i].v ,diff[i].u);
					link(diff[i].u ,diff[i].v);
					++cnt;
				}
			}
			for(rg int i = 1 ; i <= n ; ++i){
				if(!Tag[i]){
					if(!check2fen(i ,1))	LST::addedge(i ,i);
				}
			}
		}
	}
}using namespace MST;

void dp(){	//大力转移，因为本题有O2，可以放心用STL
	std::queue<int> q1 ,q2;
	for(rg int i = 1 ; i <= n ; ++i){
		vis[i][i] = true;
		DP[i][i] = true;
		q1.push(i) ,q2.push(i);
		for(rg int j = head[i] ,d ; j ; j = h[j].next){
			d = h[j].node;
			vis[i][d] = vis[d][i] = true;
			if(color[i] != color[d])	continue;
			DP[i][d] = DP[d][i] = true;
			q1.push(i) ,q2.push(d);
		}
	}
	while(!q1.empty()){
		int x = q1.front() ,y = q2.front();
		q1.pop() ,q2.pop();
		for(rg int i = head[x] ; i ; i = h[i].next){
			for(rg int j = head[y] ; j ; j = h[j].next){
				if(!vis[h[i].node][h[j].node] && color[h[i].node] == color[h[j].node]){
					DP[h[i].node][h[j].node] = DP[h[j].node][h[i].node] = true;
					q1.push(h[i].node) ,q2.push(h[j].node);
				}vis[h[i].node][h[j].node] = vis[h[j].node][h[i].node] = true;
			}
		}
	}
}

int main(){
	
	scanf("%d%d%d" ,&n ,&m ,&q);
	for(rg int i = 1 ; i <= n ; ++i){
		scanf("%1d" ,color + i);
	}
	for(rg int i = 1 ,u ,v ; i <= m ; ++i){
		scanf("%d%d" ,&u ,&v);
		FS::addedge(u ,v);
		FS::addedge(v ,u);
		if(color[u] ^ color[v])	diff[++cd] = (ip){u ,v};
		else same[++cs] = (ip){u ,v};
	}
	using namespace MST;
	kruskal(1);
	kruskal(2);
	//outedge();
	dp();
	for(rg int i = 1 ,u ,v ; i <= q ; ++i){
		scanf("%d%d" ,&u ,&v);
		if(DP[u][v] || DP[v][u])	puts("YES");
		else puts("NO");
	}
	return 0;
}