Note: This article is available in Chinese only. 本文暂无英文版本。
View original
“… so forward this to ten other people, to prove that you believe the emperor has
题意是说发短信,每个人只会给一个人发,问从哪个人开始发,能传到的人最多
思路是每个人开始做一遍dfs…
毫无意外的TLE了
一个容易想到的剪枝是,如果在第i次之前的路径上的点,在之后以它作为起点遍历一定不优.
我们可以用一个数组vis标记上(注意不要和为了dfs的标记数组vis2混淆,vis2标记的主要作用是判断是否成环)
sad,看来还是要提高自己的搜索姿势啊….
1
2
3
4 /*************************************************************************
5 > File Name: code/2015summer/sea#2/B.cpp
6 > Author: 111qqz
7 > Email: rkz2013@126.com
8 > Created Time: 2015年07月28日 星期二 14时59分16秒
9 ************************************************************************/
10
11 #include<iostream>
12 #include<iomanip>
13 #include<cstdio>
14 #include<algorithm>
15 #include<cmath>
16 #include<cstring>
17 #include<string>
18 #include<map>
19 #include<set>
20 #include<queue>
21 #include<vector>
22 #include<stack>
23 #define y0 abc111qqz
24 #define y1 hust111qqz
25 #define yn hez111qqz
26 #define j1 cute111qqz
27 #define tm crazy111qqz
28 #define lr dying111qqz
29 using namespace std;
30 #define REP(i, n) for (int i=0;i<int(n);++i)
31 typedef long long LL;
32 typedef unsigned long long ULL;
33 const int N=5E4+7;
34 int a[N];
35 bool vis[N],vis2[N];
36 int u,v,n;
37 int dfs(int x)
38 {
39 int res=0;
40 vis2[x]=true;
41 int tmp = a[x];
42 if (!vis2[tmp])
43 {
44 res = dfs(tmp)+1; //当前这个认能传的长度=他传的人能传的长度+1
45 }
46 vis[x] = true;
47 vis2[x] = false;
48 return res;
49
50
51
52
53 }
54 int main()
55 {
56 int T;
57 cin>>T;
58 int cas = 0;
59 while (T--)
60 {
61 memset(vis,false,sizeof(vis));
62 cas++;
63 scanf("%d",&n);
64 for ( int i = 0 ; i < n; i++ )
65 {
66 scanf("%d %d",&u,&v);
67 a[u]=v;
68 }
69 int mx = - 1;
70 int ans;
71 for ( int i = 1 ; i <= n ; i++)
72 {
73 // memset(vis2,false,sizeof(vis2));
74 if (vis[i]) continue; //如果在上一次的dfs中经过了i,那么从i开始传播一定是之前标记i的那次开始传播的子链,一定不优.
75 int tmp = dfs(i);
76 // cout<<dfs(i,1)<<endl;
77 if (tmp>mx)
78 {
79 mx = tmp;
80 ans = i;
81 }
82 }
83 printf("Case %d: %d\n",cas,ans);
84
85 }
86
87 return 0;
88 }