今天切了一道被推荐为树形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 阅读(455)
评论(0) 编辑 收藏 引用 所属分类:
Problem Solving