7-16 喊山-白红宇

7-16 喊山

阅读量：4113 次

发布时间：2019-05-25

本文共 2034 字，大约阅读时间需要 6 分钟。

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

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

输入格式：

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

输出格式：

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

输入样例：

7 5 41 22 33 14 55 61 4 5 7

输出样例：

思路：一开始我是用dfs写的找最远的结点，但是可能由于最小编号的原因导致结果错误，改为用bfs写，用两个数组标记每个节点，一个用于标记这个节点有没有访问过，另一个用于标记最大的层数。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;int n,m,k;const int maxn=1e4+10;vector
               
                 v[maxn];bool vis[maxn];int leve[maxn];void bfs(int x){ int ans=maxn; queue
                
                  p; p.push(x); int maxx=0; while(!p.empty()) { int u=p.front(); p.pop(); vis[u]=true; if(leve[u]>maxx) { maxx=leve[u]; ans=maxn; } if(u!=x) { ans=min(ans,u); } for(int i=0; i
                 
                  >n>>m>>k; memset(vis,false,sizeof(vis)); for(int i=0; i
                  
                   >x>>y; v[x].push_back(y); v[y].push_back(x); } while(k--) { int x; cin>>x; memset(vis,false,sizeof(vis)); memset(leve,0,sizeof(leve)); bfs(x); } return 0;}

通过伙伴的帮助，找到了错误地方，数组开小了，下面pa应该是二倍

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;const int maxn=3000+10;int G[maxn][maxn];int vis[maxn];int pa[maxn];int n,m,s;int top;void dfs(int x){ pa[top++]=x; for(int i=1; i<=n; i++) { if(G[x][i]==1&&vis[i]==0) { vis[i]=1; dfs(i); pa[top++]=x; } }}int main(){ cin>>n>>m>>s; top=0; memset(G,0,sizeof(G)); memset(vis,0,sizeof(vis)); memset(pa,0,sizeof(pa)); for(int i=0; i
               
                >x>>y; G[x][y]=G[y][x]=1; } vis[s]=1; dfs(s); if(top!=2*n-1) pa[top++]=0; for(int i=0; i

转载地址：http://tfgsi.baihongyu.com/

你可能感兴趣的文章