今天切了一道被推薦為樹形DP的題目，想了一會就想出方法了，不過調了不少時間。感覺這個題目只是一個普通的樹的題目，不過如果這也算樹形DP的話，就是我的第一道（值得紀念了）
題目模型描述：
有N個節點，每個節點有一個權值，這N個節點通過M條邊連解，任意兩個點之間有且只有一條路徑——就是樹了！(1 ≤ N ≤ 100000, 1 ≤ M ≤ 1000000),將其分為兩棵樹，使得這兩棵樹的權值相差最小，求這個最小值。
解題過程：
我開始一直以為這個題目很難——畢竟是樹形DP，后面推出這個題目可以通過DFS來做，然后寫了，交上去得到TLE，然后我懷疑方法不對，不過我刪去了最后的刪掉鄰接鏈表的操作后得到WA，這樣我繼續調試，看了DISCUSS發現要用Int64,這樣就AC了，但是效率不夠……不過先發在這里，下午再去找人問高效的算法……
這個題目注意的地方（對于我的算法）：
注意數據大小不能為int，這樣會wa
建樹時得到的鄰接鏈表在用完后不要一個一個去delete，這樣會TLE
對于N＝1的情況，可以認為還有一組0個
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-2-29 11:56:06
4 Problem Source: POJ3140
5 Description:
6
7 ********************************************************************/
8
9 # include <iostream>
10 using namespace std;
11
12 # define N 100010
13
14 typedef struct _node {
15 _node *next;
16 int id;
17 };
18
19 _node vect[ N ];
20 __int64 num[ N ], f[ N ], ans, tot;
21 int n, m;
22 bool flag[ N ];
23
24 void initialize(int n)
25 {
26 for (int i = 1; i <= n; i ++)
27 {
28 vect[i].next = NULL;
29 }
30 }
31
32 void insert(int v, int u)
33 {
34 _node *p;
35 p = new _node;
36 p->id = u;
37 p->next = vect[v].next;
38 vect[v].next = p;
39 p = new _node;
40 p->id = v;
41 p->next = vect[u].next;
42 vect[u].next = p;
43 }
44 /*
45 void del(_node *p)
46 {
47 if (p == NULL) return ;
48 del(p->next);
49 delete p;
50 }
51
52 void clear(int n)
53 {
54 for (int i = 1; i <= n; i ++)
55 {
56 del(vect[i].next);
57 vect[i].next = NULL;
58 }
59 }
60 */
61
62 void init()
63 {
64 tot = 0;
65 for (int i = 1; i <= n; i ++)
66 {
67 scanf("%I64d", &num[i]);
68 tot += num[i];
69 }
70 ans = tot;
71
72 memset(flag, false, sizeof(flag));
73 int s, t;
74 for (int i = 1; i <= m; i ++)
75 {
76 scanf("%d %d", &s, &t);
77 insert(s, t);
78 }
79 }
80
81 void output(int ca)
82 {
83 printf("Case %d: %I64d\n", ca, ans);
84 }
85
86 __int64 DFS(int now)
87 {
88 if (ans < 2) return tot;
89 f[ now ] = num[now];
90 _node *p = vect[now].next;
91 flag[now] = true;
92 while (p != NULL)
93 {
94 if (!flag[p->id]) f[now] += DFS(p->id);
95 p = p->next;
96 }
97 __int64 tmp = abs(tot - 2*f[now]);
98 if (tmp < ans) ans = tmp;
99 return f[ now ];
100 }
101
102 int main()
103 {
104 int ca = 0;
105 while (true)
106 {
107 scanf("%d %d", &n, &m);
108 if (n == 0 && m == 0) break; ca ++;
109 initialize(n);
110 init();
111 DFS(1);
112 output(ca);
113 // clear(n);
114 }
115 return 0;
116 }
117
118
posted on 2008-02-29 14:09
R2 閱讀(498)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving