L3-008 喊山（30 分)

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。（图文摘自：http://news.xrxxw.com/newsshow-8018.html）
L3-008 喊山（30 分)

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：
输入第一行给出3个正整数n、m和k，其中n（≤10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（≤10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：
依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：
7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7
输出样例：
2
6
4
0

这个题目最神奇的地方就是
我没懂,我没测,我敲了,我A了
不是说只能传到相邻两座山么,为什么还能传递的传呢
可能当时限制人们通讯的不是纸张,是声速了
题意猜测是搞一个bfs,判断包含当前节点的连通块的大小
如果为空则为0,否则输出连通块大小
bfs模板写一下就可以liao

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//Constant area
const int MAXN=1000000;
const int MIN_INF=0x80000000;
const int MAX_INF=0x7fffffff;
//Variable area
int n,m,k;
int beg[201000];
int nex[200100];
int to[200100];
int e;
int maxdepth;
int ans;
bool vis[20100];
struct p{
	int depth;
	int self;
};
//Initialization area
void init(){
	memset(beg,-1,sizeof(beg));
	e=0;
    return;
}
//Function area
void add(int a,int b){
	nex[++e]=beg[a];
	beg[a]=e;
	to[e]=b;
}
queue<p> q;
void search(int st){
	maxdepth=0;
	ans=MAX_INF;
	memset(vis,0,sizeof(vis));
	while(q.size())
		q.pop();
	q.push({0,st});
	int cal=0;
	vis[st]=true;
	while(q.size()){
		p now=q.front();
		if(maxdepth<=now.depth){
			if(maxdepth==now.depth)
				ans=min(ans,now.self);
			else
				ans=now.self;
			maxdepth=now.depth;
		}
		q.pop();
		cal++;
		for(int i=beg[now.self];i!=-1;i=nex[i]){
			if(vis[to[i]])
				continue;
			vis[to[i]]=true;
			q.push({now.depth+1,to[i]});
		}
	}
}
int main(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
    	int a,b;
    	cin>>a>>b;
    	add(a,b);
    	add(b,a);
	}
	for(int i=1;i<=k;i++){
		int te;
		cin>>te;
		search(te);
		if(maxdepth==0)
			cout<<0<<endl;
		else
			cout<<ans<<endl;
	}
}

最后武玉泰要是看到这里的话,请问你还记得当时西区的肉丸子吗嘤嘤嘤~

L3-008 喊山 （30 分)

相关推荐

L3-008 喊山（30 分)