“… 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 }