P8287 「DAOI R1」Flame

题目背景

尝尝天堂里的苹果有什么了不起，我要尝尝地狱里的苹果。

题目描述

黑暗里有黑色的火焰，只有目光敏锐的人才可以捕捉到,

借着这点卑微之光,走进地狱深处…

欢迎来到地狱的审判之地。

$ \texttt{hhpq.} $ 将 D 押入了地狱的审判之地，D 必须在业火之城成功生成一座业火监狱之前逃离，所以他想知道还有多少秒时间。

在这座业火之城中，共有 $n$ 个祭坛，共有 $m$ 条可以蔓延火苗的业火之路，且业火之路是双向连通。

已知在这一座业火之城共有 $k$ 个火种已被点燃的业火祭坛，且从第一秒开始，火种将开始从被点燃的业火祭坛向可以蔓延且未被点燃的业火祭坛蔓延。

当祭坛被点燃后，则会瞬间激活，和与之有路的祭坛连接业火圣壁。

当存在一片由业火圣壁构成的封闭图形时，则业火监狱生成成功。

简化题意

给出一个 $n$ 个点，$m$ 条边的无向图，每一个点有一个标记，初始有 $k$ 个点的标记为 1（将给出这 $k$ 个点的编号），其余的点标记为 0。

每一秒，对于每个标记为 1 的点，与它有边相连的点的标记都会变成 1。

求最少需要多少秒，图中标记为 1 的点与其相邻的边可以构成一个简单环。

换言之，求最少多少秒后存在一个由 1 构成的集合形成简单环。

输入格式

第一行三个正整数：$n,m,k$；

下面 $m$ 行，每行两个正整数：$x,y$（第 $x$ 座业火祭坛与第 $y$ 座业火祭坛有业火之路连接）；

最后一行 $k$ 个正整数：已被点燃（拥有火种）的祭坛编号。

输出格式

若可以逃离，输出 D 还有多少时间。

反之若无法生成业火监狱，输出 Poor D! 。

输入输出样例 #1

输入 #1

3 3 1
1 2
2 3
3 1
1

输出 #1

1

输入输出样例 #2

输入 #2

5 4 2
1 2
2 3
3 4
2 5
1 5

输出 #2

Poor D!

输入输出样例 #3

输入 #3

15 15 2
2 1
2 3
2 9
5 9
4 5
5 7
6 7
7 8
7 11
11 10
10 9
10 14
14 15
11 12
12 13
4 15

输出 #3

3

说明/提示

样例解释

样例1解释

当时间到第一秒时，祭坛 $1$ 的火焰将蔓延到祭坛 $2$ 和 $3$，此时已经构成一个封闭图形了，故答案为 $1$。

样例2解释

可以证明到此时是无法产生简单环的。

数据规模

Subtask	$n\le$	$m\le$	$k\le$	分值
$0$	$10^6$	$n-1$	$10^4$	$5$
$1$	$10^6$	$2\times 10^6$	$1$	$10$
$2$	$10$	$45$	$1$	$5$
$3$	$200$	$500$	$10$	$10$
$4$	$2\times 10^3$	$5\times 10^3$	$50$	$10$
$5$	$5\times 10^5$	$6\times 10^5$	$500$	$30$
$6$	$10^6$	$2\times 10^6$	$10^4$	$30$

保证与约定

保证数据无重边和自环；

保证数据给定的图是一张无向连通图。

帮助

输入量较大，建议使用较为快速的读入方式。

C++实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int Max = 1000005;
int n, m, k, ans = Max, f[Max], dis[Max];
vector<int> g[Max];
queue<pair<int, int>> q;
bool vis[Max];
int father(int x) { // 并查集 
	if (f[x] == x)
		return x;
	return f[x] = father(f[x]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    if (m == n - 1) { // 判定无解 
        cout << "Poor D!" << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++) // 并查集初始化 
    	f[i] = i;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1, x; i <= k; i++) {  
        cin >> x;
        q.push(make_pair(x, 0)); // 搜索由 k 个源点同时开始 
        dis[x] = 1;
    }
	while (!q.empty()) {
		int x = q.front().first; // 当前节点 
		int fa = q.front().second; // 父节点 
		q.pop();
		if (vis[x])  
			continue;
		vis[x] = true;
		for (auto y: g[x]) 
			if (y != fa) { // 跳过父节点 
				if (!dis[y]) {
					dis[y] = dis[x] + 1;
					q.push(make_pair(y, x));
					f[father(y)] = father(x);
				} else if (!(dis[y] + 1 == dis[x] || (vis[y] && dis[y] == dis[x]))) {
					if (father(y) == father(x)) // 已经同属一个集合 统计答案 
						ans = min(max(dis[y], dis[x]) - 1, ans);
					else
						f[father(y)] = father(x);
				}
			}
	}
	cout << ans << endl;
	return 0; 
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容