hdu 4514 湫湫系列故事——设计风景线（树DP）

Problem - 4514

　　这是今晚的腾讯第三场初赛题中的1005。虽然我没有参加这场比赛，不过我还是尝试做了一下今晚的变态题。

　　这道题是要你判一幅图中是否有环，有环的话就输出“YES”，没有的话就输出森林里最长的一条路径。题目是中文的，就解释这么多吧！

　　做法就是直接dfs，每次保存两个值，一个是子树单链的最长长度，另一个是子树中最长的完整链的长度。

　　不过dfs有一个问题就是会爆栈，如果不想改bfs的话就要加上栈挂。

　　哈哈，最意想不到的是我居然一次做就对树DP了，除了那狗血的RE。-.-

代码如下：

View Code

 1 #pragma comment(linker, "/STACK:102400000,102400000")
 2 
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <vector>
 7 #include <algorithm>
 8 #include <set>
 9 #include <iostream>
10 #include <map>
11 
12 using namespace std;
13 
14 #define REP(i, n) for (int i = 0; i < (n); i++)
15 #define REP_1(i, n) for (int i = 1; i <= (n); i++)
16 #define PB push_back
17 #define MPR make_pair
18 #define SZ(x) ((int) (x).size())
19 #define FI first
20 #define SE second
21 #define _clr(x) memset(x, 0, sizeof(x))
22 #define ALL(x) (x).begin(), (x).end()
23 
24 typedef vector<int> VI;
25 typedef pair<int, int> PII;
26 typedef vector<PII> VPII;
27 
28 const int N = 1e5 + 100;
29 
30 bool vis[N];
31 VPII rel[N];
32 
33 void input(int n, int m) {
34     REP_1(i, n) rel[i].clear();
35     int x, y, w;
36     REP(i, m) {
37         scanf("%d%d%d", &x, &y, &w);
38         rel[x].PB(MPR(y, w));
39         rel[y].PB(MPR(x, w));
40     }
41 }
42 
43 PII dfs(int x) {
44     VI dis;
45     dis.clear();
46     int cnt = 0, mx = 0;
47     vis[x] = true;
48     REP(i, SZ(rel[x])) {
49         int y = rel[x][i].FI, d = rel[x][i].SE;
50         if (vis[y]) {
51             cnt++;
52             if (cnt > 1) return MPR(-1, -1);
53             continue;
54         }
55         PII tmp = dfs(y);
56         if (~tmp.FI) {
57             dis.PB(d + tmp.FI);
58             mx = max(mx, tmp.SE);
59         } else {
60             return MPR(-1, -1);
61         }
62     }
63     sort(ALL(dis));
64     int sz = SZ(dis);
65     if (sz >= 2) return MPR(dis[sz - 1], max(dis[sz - 1] + dis[sz - 2], mx));
66     else if (sz == 1) return MPR(dis[sz - 1], dis[sz - 1]);
67     else return MPR(0, 0);
68 }
69 
70 int work(int n) {
71     int mx = 0;
72     _clr(vis);
73     REP_1(i, n) {
74         if (!vis[i]) {
75             int tmp = dfs(i).SE;
76             if (~tmp) mx = max(mx, tmp);
77             else return -1;
78         }
79     }
80     return mx;
81 }
82 
83 int main() {
84     int n, m;
85     while (~scanf("%d%d", &n, &m)) {
86         input(n, m);
87         int ans = work(n);
88         if (~ans) printf("%d\n", ans);
89         else puts("YES");
90     }
91     return 0;
92 }

——written by Lyon