HDU 2242 考研路茫茫——空调教室

考研路茫茫——空调教室

http://acm.hdu.edu.cn/showproblem.php?pid=2242

分析：

　　树形dp，删边。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int MAXN = 10010;
 8 const int MAXM = 50010;
 9 
10 struct Edge{
11     int to,nxt;
12 }e[MAXM];
13 int head[MAXM],tot;
14 int son[MAXN],Sum,ans;
15 
16 inline int read() {
17     int x = 0,f = 1;char ch = getchar();
18     for (; ch<'0'||ch>'9'; ch = getchar())
19         if (ch=='-') f = -1;
20     for (; ch>='0'&&ch<='9'; ch = getchar())
21         x = x*10+ch-'0';
22     return x*f;
23 }
24 inline void add_edge(int u,int v) {
25     e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot;
26 }
27 inline void init() {
28     memset(head,0,sizeof(head));
29     ans = 1e9; // ans也要初始化！！！ 
30     tot = Sum = 0;
31 }
32 void dfs(int u,int fa) {
33     for (int i=head[u]; i; i=e[i].nxt) {
34         int v = e[i].to;
35         if (v==fa) continue;
36         dfs(v,u);
37         son[u] += son[v];
38         ans = min(ans,abs(Sum-son[v]-son[v]));
39     }
40 }
41 
42 int main() { 
43     int n,m,CASE = 0;
44     while (scanf("%d%d",&n,&m)!=EOF) {
45         init();
46         for (int i=1; i<=n; ++i) son[i] = read(),Sum += son[i];
47         for (int u,v,i=1; i<=m; ++i) {
48             u = read(),v = read();
49             add_edge(u,v),add_edge(v,u);
50         }
51         dfs(0,-1);
52         printf("Case %d: %d
",++CASE,ans);
53     }
54     return 0;
55 }