May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0
   今天切了一道被推荐为树形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 < 2return tot;
 89     f[ now ] = num[now];
 90     _node *= 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 == 0break; 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 阅读(461) 评论(0)  编辑 收藏 引用 所属分类: Problem Solving

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


你是第 free hit counter 位访客




<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 62814
  • 排名 - 356

最新评论

阅读排行榜

评论排行榜