HDU 4714 Tree2Cycle

　　简单的DFS 有些大神有树形DP做的，效率要高很多。

　　若degree[i] > 2 ,则断开 i 与其父节点之间的边和 degree[i] - 3 个子节点之间的边,其父节点度减一。

　　此时总消费增加 sum += (degree[i] - 2)*2;

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <queue>
 7 #include <vector>
 8 #pragma comment(linker,"/STACK:102400000,102400000")
 9 
10 using namespace std;
11 
12 struct E
13 {
14     int v,next;
15 } edge[2001000];
16 
17 int head[1001000];
18 
19 int top,sum;
20 
21 void link(int u,int v)
22 {
23     edge[top].v = v;
24     edge[top].next = head[u];
25     head[u] = top++;
26 }
27 
28 bool visit[1000100];
29 
30 int dfs(int st)
31 {
32     int i;
33 
34     i = head[st];
35     if(i == -1)//此时st点为叶子
36     {
37         return 1;
38     }
39 
40     int ans = 0;
41 
42     visit[st] = true;
43 
44     while(i != -1)
45     {
46         if(visit[edge[i].v] == false)
47         {
48             visit[edge[i].v] = true;
49             ans += dfs(edge[i].v);
50         }
51         i = edge[i].next;
52     }
53 
54 
55     if(ans <= 1)
56         return 1;
57     if(st == 1)
58         sum += (ans -2)*2;
59     else
60         sum += (ans-1)*2;
61     return 0;
62 
63 }
64 
65 int main()
66 {
67     int T;
68     int n,i,u,v;
69 
70     scanf("%d",&T);
71 
72     while(T--)
73     {
74         top = 0;
75         sum = 0;
76 
77         scanf("%d",&n);
78 
79         memset(head,-1,(n+2)*sizeof(int));
80         memset(visit,false,(n+2)*sizeof(bool));
81 
82         for(i = 1; i < n; ++i)
83         {
84             scanf("%d %d",&u,&v);
85             link(u,v);
86             link(v,u);
87         }
88 
89         dfs(1);
90         printf("%d
",++sum);
91     }
92     return 0;
93 }

View Code