CCF 201503-4 网络延时

试题编号：	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<iostream>
  5 #include<iomanip>
  6 #include<cstdio>
  7 #include<string>
  8 #include<sstream>
  9 #include<map>
 10 #include<list>
 11 #include<algorithm>
 12 #include<cmath> 
 13 using namespace std;
 14 #define YCOL1 10
 15 struct yc2il{
 16     int v;//遍历标志 0未
 17     int lay;//层次(0s) 
 18     list<int> 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<int>::const_iterator it = st.li.begin();it!=st.li.end();it++){
 33         os << *it << "=>";
 34     } 
 35     return os;
 36 }
 37 //二维数组
 38 template<typename T>
 39 void yPrintArr(const T x[][YCOL1]){
 40     int i = 0;
 41     while(1){
 42         cout << i;
 43         for(int j = 0;j<ydelom;j++){
 44             cout << " (" << j << "," << x[i][j] << ")";
 45         }
 46         i++;
 47         if(i >= ydelon){
 48             break;
 49         }
 50         else{
 51             cout << endl;
 52         }
 53     }
 54     return;
 55 }
 56 template<typename T>
 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<typename T,int size>
 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<typename T,int size>
 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<typename T>
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 & map
123 template<typename T,typename S>
124 ostream &operator<<(ostream &os,const pair<T,S> &it){
125     return     os << it.first << " " << it.second;
126 }
127 template<typename T,typename S>
128 ostream &operator<<(ostream &os,const map<T,S> &st){
129     int n = ydelon==0?st.size():ydelon,i = 0;
130     os <<  " size=" << st.size() << " show=" << n << endl;
131     for(typename map<T,S>::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<typename T>
144 ostream &operator<<(ostream &os,const list<T> &st){
145     int n = ydelon==0?st.size():ydelon,i = 0;
146     os <<  " size=" << st.size() << " show=" << n << endl;
147     for(typename list<T>::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 #endif
160 
161 int main(){
162     #ifdef YLOFI
163     freopen("yin.txt","r",stdin);
164     //freopen("yout.txt","w",stdout);
165     #endif
166     #ifdef YDELO
167     assert(1);
168     #endif
169     int nr = 0;
170     int nt = 0;
171     cin >> nr >> nt;
172     map<int,yc2il> ma;//设备联通关系图 K:设备号 正路由(1s)负电脑 V:邻接表
173     yc2il bufy1;
174     bufy1.v = 0;
175     ma[1] = bufy1;
176     //路由器 
177     for(int i = 0;i<nr-1;i++){
178         int bufi1 = 0;
179         cin >> 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<nt;i++){
188         int bufi1 = 0;
189         cin >> 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 YDELO
197     assert(yPrint("ma",ma,0,false)); 
198     #endif
199     //第一次最远点 
200     list<int> 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<int>::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 YDELO
215     assert(yPrint("head",head,0,false)); 
216     #endif
217     //第二次最远点
218     //1)清空访问标志
219     for(map<int,yc2il>::iterator it = ma.begin();it != ma.end();it++){
220         it->second.v = 0;
221     }
222     #ifdef YDELO
223     assert(yPrint("ma 2",ma,0,false)); 
224     #endif
225     //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<int>::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 YDELO
241     assert(yPrint("ma 3",ma,0,false)); 
242     #endif
243     cout << ma[head].lay;
244     return 0;
245 }