CCF 201503-4 网络延时-白红宇

CCF 201503-4 网络延时

阅读量：6087 次

发布时间：2019-06-20

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

试题编号：	201503-4
试题名称：	网络延时
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　给定一个公司的网络，由 n台交换机和 m台终端电脑组成，交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置，编号为1的交换机为根交换机，层级为1。其他的交换机都连接到一台比自己上一层的交换机上，其层级为对应交换机的层级加1。所有的终端电脑都直接连接到交换机上。　　当信息在电脑、交换机之间传递时，每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问，电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。输入格式　　输入的第一行包含两个整数 n, m，分别表示交换机的台数和终端电脑的台数。　　第二行包含 n - 1个整数，分别表示第2、3、……、 n台交换机所连接的比自己上一层的交换机的编号。第 i台交换机所连接的上一层的交换机编号一定比自己的编号小。　　第三行包含 m个整数，分别表示第1、2、……、 m台终端电脑所连接的交换机的编号。输出格式　　输出一个整数，表示消息传递最多需要的步数。样例输入 4 2 1 1 3 2 1 样例输出 4 样例说明　　样例的网络连接模式如下，其中圆圈表示交换机，方框表示电脑：　　其中电脑1与交换机4之间的消息传递花费的时间最长，为4个单位时间。样例输入 4 4 1 2 2 3 4 4 4 样例输出 4 样例说明　　样例的网络连接模式如下：　　其中电脑1与电脑4之间的消息传递花费的时间最长，为4个单位时间。评测用例规模与约定　　前30%的评测用例满足： n ≤ 5, m ≤ 5。　　前50%的评测用例满足： n ≤ 20, m ≤ 20。　　前70%的评测用例满足： n ≤ 100, m ≤ 100。　　所有评测用例都满足：1 ≤ n ≤ 10000，1 ≤ m ≤ 10000。

关键词：bfs、不要递归（会爆栈）、list+map完美调试、树的直径问题（两次最远点）

1 //#define YLOFI  2 //#define YDELO  3   4 #include
     
        5 #include
      
         6 #include
       
          7 #include
        
           8 #include
         
            9 #include
           10 #include
           
             11 #include
            
              12 #include
             
               13 using namespace std; 14 #define YCOL1 10 15 struct yc2il{ 16 int v;//遍历标志 0未 17 int lay;//层次(0s) 18 list
              
                li;//邻接表 19 }; 20 21 22 23 #ifdef YDELO 24 //#include "YLog.h" 25 #include "assert.h" 26 int ydelon = 0; 27 int ydelom = 0; 28 29 //自定义 30 ostream &operator<<(ostream &os,const yc2il &st){ 31 os << "v=" << st.v << " lay=" << st.lay << " li(size=" << st.li.size() << ")="; 32 for(list
               
                ::const_iterator it = st.li.begin();it!=st.li.end();it++){ 33 os << *it << "=>"; 34 } 35 return os; 36 } 37 //二维数组 38 template
                
                  39 void yPrintArr(const T x[][YCOL1]){ 40 int i = 0; 41 while(1){ 42 cout << i; 43 for(int j = 0;j
                 
                  = ydelon){ 48 break; 49 } 50 else{ 51 cout << endl; 52 } 53 } 54 return; 55 } 56 template
                  
                    57 bool yPrint(const string &info,const T x[][YCOL1],int n = 0,int m = 0,bool clr = true){ 58 if(clr){ 59 system("cls"); 60 } 61 cout << endl << "\\**********************" << endl << info << endl; 62 ydelon = n; 63 ydelom = m; 64 if(ydelon > 0 && ydelom > 0){ 65 yPrintArr(x); 66 } 67 else{ 68 return false; 69 } 70 cout << endl << "**********************\\" << endl; 71 return true; 72 } 73 //数组 74 template
                   
                     75 void yPrintArr(const T (&x)[size]){ 76 int i = 0; 77 while(1){ 78 cout << i << " " << x[i]; 79 i++; 80 if(i >= ydelon){ 81 break; 82 } 83 else{ 84 cout << endl; 85 } 86 } 87 return; 88 } 89 template
                    
                      90 bool yPrint(const string &info,const T (&x)[size],int n = 0,bool clr = true){ 91 if(clr){ 92 system("cls"); 93 } 94 cout << endl << "\\**********************" << endl << info << endl; 95 ydelon = n; 96 if(ydelon > 0){ 97 yPrintArr(x); 98 } 99 else{100 return false;101 }102 cout << endl << "**********************\\" << endl;103 return true;104 }105 //非数组106 template
                     
                      107 bool yPrint(const string &info,const T &x,int n = 0,bool clr = true){108 if(clr){109 system("cls");110 }111 cout << endl << "\\**********************" << endl << info << endl;112 ydelon = n;113 if(ydelon >= 0){114 cout << x;115 }116 else{117 return false;118 }119 cout << endl << "**********************\\" << endl;120 return true;121 }122 //list & map123 template
                      
                       124 ostream &operator<<(ostream &os,const pair
                       
                         &it){125 return os << it.first << " " << it.second;126 }127 template
                        
                         128 ostream &operator<<(ostream &os,const map
                         
                           &st){129 int n = ydelon==0?st.size():ydelon,i = 0;130 os << " size=" << st.size() << " show=" << n << endl;131 for(typename map
                          
                           ::const_iterator it = st.begin();it!=st.end();it++){132 os << i << " " << *it;133 i++;134 if(i >= n){135 break;136 }137 else{ 138 os << endl;139 }140 }141 return os;142 }143 template
                           
                            144 ostream &operator<<(ostream &os,const list
                            
                              &st){145 int n = ydelon==0?st.size():ydelon,i = 0;146 os << " size=" << st.size() << " show=" << n << endl;147 for(typename list
                             
                              ::const_iterator it = st.begin();it!=st.end();it++){148 os << i << " " << *it;149 i++;150 if(i >= n){151 break;152 }153 else{154 os << endl;155 }156 }157 return os;158 }159 #endif160 161 int main(){162 #ifdef YLOFI163 freopen("yin.txt","r",stdin);164 //freopen("yout.txt","w",stdout);165 #endif166 #ifdef YDELO167 assert(1);168 #endif169 int nr = 0;170 int nt = 0;171 cin >> nr >> nt;172 map
                              
                                ma;//设备联通关系图 K:设备号 正路由(1s)负电脑 V:邻接表173 yc2il bufy1;174 bufy1.v = 0;175 ma[1] = bufy1;176 //路由器 177 for(int i = 0;i
                               
                                > bufi1;180 ma[bufi1].li.push_back(i+2);181 yc2il bufy2;182 bufy2.v = 0;183 bufy2.li.push_back(bufi1);184 ma[i+2] = bufy2;185 }186 //电脑 187 for(int i = 0;i
                                
                                 > bufi1;190 ma[bufi1].li.push_back(-i-1);191 yc2il bufy2;192 bufy2.v = 0;193 bufy2.li.push_back(bufi1);194 ma[-i-1] = bufy2;195 }196 #ifdef YDELO197 assert(yPrint("ma",ma,0,false)); 198 #endif199 //第一次最远点 200 list
                                 
                                   li;//遍历队列 V:设备号201 li.push_back(1);202 ma[1].v = 1; 203 int head = 0; 204 while(!li.empty()){205 head = li.front();206 li.pop_front();207 for(list
                                  
                                   ::iterator it = ma[head].li.begin();it != ma[head].li.end();it++){208 if(!ma[*it].v){209 li.push_back(*it);210 ma[*it].v = 1;211 }212 }213 }214 #ifdef YDELO215 assert(yPrint("head",head,0,false)); 216 #endif217 //第二次最远点218 //1)清空访问标志219 for(map
                                   
                                    ::iterator it = ma.begin();it != ma.end();it++){220 it->second.v = 0;221 }222 #ifdef YDELO223 assert(yPrint("ma 2",ma,0,false)); 224 #endif225 //2)获取最深层次 226 li.push_back(head);227 ma[head].v = 1;228 ma[head].lay = 0; 229 while(!li.empty()){230 head = li.front();231 li.pop_front();232 for(list
                                    
                                     ::iterator it = ma[head].li.begin();it!=ma[head].li.end();it++){233 if(!ma[*it].v){234 li.push_back(*it);235 ma[*it].v = 1;236 ma[*it].lay = ma[head].lay + 1;237 }238 }239 }240 #ifdef YDELO241 assert(yPrint("ma 3",ma,0,false)); 242 #endif243 cout << ma[head].lay;244 return 0;245 }