当前位置：首页 > news >正文

打卡信奥刷题（3220）用C++实现信奥题 P8287 「DAOI R1」Flame

news 2026/5/7 2:38:08

P8287 「DAOI R1」Flame

题目背景

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

题目描述

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

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

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

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

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

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

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

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

简化题意

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

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

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

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

输入格式

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

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

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

输出格式

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

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

输入输出样例 #1

输入 #1

3 3 1 1 2 2 3 3 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

说明/提示

样例解释

样例1解释

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

样例2解释

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

数据规模

Subtask	n≤n\leqn≤	m≤m\leqm≤	k≤k\leqk≤	分值
000	10610^6106	n−1n-1n−1	10410^4104	555
111	10610^6106	2×1062\times10^62×106	111	101010
222	101010	454545	111	555
333	200200200	500500500	101010	101010
444	2×1032\times 10^32×103	5×1035\times 10^35×103	505050	101010
555	5×1055\times10^55×105	6×1056\times10^56×105	500500500	303030
666	10610^6106	2×1062\times10^62×106	10410^4104	303030

保证与约定

保证数据无重边和自环；

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

帮助

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

C++实现

#include<iostream>#include<vector>#include<queue>usingnamespacestd;constintMax=1000005;intn,m,k,ans=Max,f[Max],dis[Max];vector<int>g[Max];queue<pair<int,int>>q;boolvis[Max];intfather(intx){// 并查集if(f[x]==x)returnx;returnf[x]=father(f[x]);}intmain(){ios::sync_with_stdio(false);cin>>n>>m>>k;if(m==n-1){// 判定无解cout<<"Poor D!"<<endl;return0;}for(inti=1;i<=n;i++)// 并查集初始化f[i]=i;for(inti=1,x,y;i<=m;i++){cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}for(inti=1,x;i<=k;i++){cin>>x;q.push(make_pair(x,0));// 搜索由 k 个源点同时开始dis[x]=1;}while(!q.empty()){intx=q.front().first;// 当前节点intfa=q.front().second;// 父节点q.pop();if(vis[x])continue;vis[x]=true;for(autoy:g[x])if(y!=fa){// 跳过父节点if(!dis[y]){dis[y]=dis[x]+1;q.push(make_pair(y,x));f[father(y)]=father(x);}elseif(!(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);elsef[father(y)]=father(x);}}}cout<<ans<<endl;return0;}