codeforces 615 B. Longtail Hedgehog (DFS + 剪枝)

题目链接：

题目描述：

　　给定n个点m条无向边的图，设一条节点递增的链末尾节点为u，链上点的个数为P，则该链的beauty值 = P*degree[u]。问你所有链中最大的beauty值。

解题思路：

　　因为只需要找到以每个节点为终点的最长递增链即可，所以建图的时候可以建成从编号小的节点到编号大的节点的有向图，然后用DFS搜索，但是直接暴搜会TLE，然后就开始了我的TLE之路，TLE24， TLE42，TLE56，TLE60.....，准备弃疗时，学弟帮我看了一下，竟然改对了，而且跑得飞快(✪▽✪)，就是定义一个标志数组，记录当前节点之前的节点是不是已经遍历完了，如果遍历完了，那么当前节点就是最优的了，就从当前节点向下遍历。新技能get√

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 using namespace std;
 9 #define LL __int64
10 
11 const LL INF = 1e9+7;
12 const int maxn = 100010;
13 struct node
14 {
15     int to, next;
16 } edge[maxn*4];
17 
18 
19 int head[maxn], tot, du[maxn], in[maxn];
20 LL ans[maxn];
21 
22 void add (int from, int to)
23 {
24     edge[tot].to = to;
25     edge[tot].next = head[from];
26     head[from] = tot ++;
27 }
28 /**
29     记录in[i]为i点的入度
30     当入度为零时，当前节点更新为最优，
31     然后从当前节点继续向下遍历
32     向下遍历时层数参数为当前层加一
33     而不是简单的上一层参数加一
34 */
35 void dfs (int u, LL x)
36 {
37     
38     for (int i=head[u]; i!=-1; i=edge[i].next)
39     {
40         int v = edge[i].to;
41         ans[v] = max (ans[v], x);
42         in[v]--;
43 
44         if(in[v] == 0)
45             dfs (v, ans[v]+1);
46     }
47 }
48 
49 int main ()
50 {
51     int n, m;
52 
53     scanf ("%d %d", &n, &m);
54     memset (head, -1, sizeof(head));
55     tot = 0;
56 
57     for (int i=0; i<m; i++)
58     {
59         int u, v;
60         scanf ("%d %d", &u, &v);
61         if(u > v)
62             swap (u, v);
63         du[u] ++;
64         du[v] ++;
65         in[v]++;
66         add (u, v);
67     }
68 
69     for (int i=1; i<=n; i++)
70     {
71         if (ans[i] == 0)
72         {
73             ans[i] = 1;
74             dfs (i, 2);
75         }
76     }
77 
78     LL sum = 0;
79     for (int i=1; i<=n; i++)
80         sum = max (sum, ans[i] * du[i]);
81 
82     printf ("%I64d
", sum);
83     return 0;
84 }