526互联

Codeforces Round 847 (Div. 3) G.Tokens on Graph （构造）

发布时间 2023-04-27 11:07:12作者: qdhys

传送门

题目大意

  给定一个无向图，我们定义图中有四种点，一种是黑色的点表示终点，并且黑色的点始终是1号点，一种是红色的点，一种是灰色的点，最后一种就是没有颜色的点。

  游戏规则：我们必须移动任意一个灰色的点到相邻的点上，如果灰色的点移动到了红色的点上，那么我们可以移动其他灰色的点继续上述操作（不能移动自己），否则游戏结束。如果我们最终能使灰色的点到达终点，那么输出YES，如果不能使灰色的的点到达终点，输出NO。一下图为例：

  我们这么移动8->6，7->5，6->4, 5->6, 4->2, 6->4, 2->1游戏结束到达终点输出YES。

  输入一个整数T，表示有T组测试数据(1≤T≤1e4)。测试用例由一个空字符串分隔

  输入n和m表示有n个点m个边 (1≤n≤2e5 , 0≤m≤2e5)，并且保证图一定联通，任何点之间都是可以到达的。

  输入p和b表示有p个黑色的点和b个红色的点。其中(1≤p≤n,0≤b≤n )。也就是说可能没有红色的点。

  输入p个两两不同的灰色的点，表示灰色的点所在的位置。

  输入b个红色的点，表示红色点所在的位置（灰色点可以和红色点重合，并且一个点上可以有多个灰色点，如果b为0则这一行为空）。

  输入m行u，v表示u和v之间有一条边。

  可以保证所有测试用例的n之和不超过2e5。同样地，保证所有输入数据集的m之和不超过2e5

解题思路：

  如果有灰色的点在终点直接输出YES，或者终点附近有灰色的点直接输出YES。

  我们发现一个性质，那就是如果一个灰色的点能走到红色的点，并且这个红色的点周围也有红色的点，那么我们就可以一直在这两个红色的点之间一直走下去。所以我们把红色的点分为两类：

  1.可以走无限步数的红色的点。

  2.只能走一步的红色的点。

  我们从终点出发找到所有能到达的灰色的点，并将这些点的编号和离终点的距离丢进一个vector<pair<int, int>> use;数组里面。

  如果use为空那么一定无解。

  我们把use内的第一个元素的编号定义为st，第一个元素到终点的距离定义为sum。我们从其他所有灰色点出发，如果这些灰色的点能走出第一种红色的点那么输出YES，如果这些灰色的点能走的第二种点的数量大于等于sum-1，那么也输出YES。但是我们第一个元素不一定就是能走到终点的点，因为我们可能第一个元素能走出第一种点，那么如果存在第二个元素也可以直接输出YES。

  

#include <bits/stdc++.h>

const int N = 2e5 + 10, M = N << 2;

int n, m;
typedef long long ll;
const int INF = 0x3f3f3f3f;
typedef std::pair<int, int> PII;

int h[N], ne[N << 1], e[N << 1], idx;

inline void add(int a, int b) {
	ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}

inline void slove() {
	std::cin >> n >> m;
	std::vector<bool> grey(n, 0), red(n, 0);//i号点是不是灰色点或者红色点
	idx = 0;
	for (int i = 0; i < n; i ++) h[i] = -1;
	int p, b;
	std::cin >> p >> b;
	std::vector<int> point;//存储所有灰色点编号

	for (int i = 1; i <= p; i ++) {
		int x;
		std::cin >> x;
		x --;
		grey[x] = true;//给灰色点打标记
		point.push_back(x);
	}
	
	for (int i = 1; i <= b; i ++) {
		int x;
		std::cin >> x;
		x --;
		red[x] = true;//给红色点打标记
	}
	
	while (m --) {
		int a, b;
		std::cin >> a >> b;
		a --, b --;
		add(a, b);
		add(b, a);
	}
	
	std::vector<bool> good(n, 0);//本身是红色周围也有红色，那么到达这个点可以一直走下去。
	
	for (int i = 0; i < n; i ++) {//找到本身是红色邻边也为红色的点
		if (red[i]) {
			bool f = false;
			for (int j = h[i]; ~j; j = ne[j]) {
				int k = e[j];

				if (red[k]) {
					f = true;
					break;
				}
			}

			if (f)	good[i] = true;
		}
	}

	
	if (grey[0]) {//如果灰色点在终点直接输出YES
		std::cout << "YES" << '\n';
		return ;
	}
	
	std::vector<PII> use;//记录能到达终点的灰色点的编号和到终点的距离
	int st = -1, sum = 0;//记录离终点最近的点的编号和距离
	auto bfs = [&]() -> void {
		std::queue<PII> q;
		std::vector<bool> vis(n);
		q.push({0, 0});
		vis[0] = true;
		while (!q.empty()) {
			PII u = q.front();
			q.pop();
			for (int i = h[u.first]; ~i; i = ne[i]) {
				int j = e[i];
				if (vis[j])	continue;
				if (grey[j]) {
					if (st == -1) {
						st = j;
						sum = u.second + 1; 
					}
					use.push_back({st, u.second + 1});
				}
				if (red[j]) {
					q.push({j, u.second + 1});
					vis[j] = true;
				}
			}
		}
	};
	
	bfs();
	if (st == -1) {//如果没有灰色点可以到达终点直接输出NO即可
		std::cout << "NO" << '\n';
		return ;
	}

	bool ok = false;//ok表示是否有一个灰色的可以无限走（即能走到good的点上）
	int step = 0;
	
	for (auto &u: point) {
		if (u != st) {//判断其他点是能走的步数。
			bool f = false;
			for (int i = h[u]; ~i; i = ne[i]) {
				int j = e[i];
				if (good[j]) {
					ok = true;
					break;
				}
				if (red[j]) f = true;
			}
			if (f)	step ++;
		} else {//如果离终点最近的点可以无限走，并且还有其他可以到达终点的点直接输出YES
			for (int i = h[u]; ~i; i = ne[i]) {
				int j = e[i];
				if (ok && use.size() > 1) {
					std::cout << "YES" << '\n';
					return ;
				}
			}
		}
		if (ok) break;
	}
	
	if (ok || sum == 1) std::cout << "YES" << '\n';
	else if (step >= sum - 1) std::cout << "YES" << '\n';
	else std::cout << "NO" << '\n';
}

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int _ = 1;
	std::cin >> _;
	while (_ --) slove();
	
	return 0;
}