2015 Multi-University Training Contest 1 hdu 5290 Bombing plan

Bombing plan

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 416 Accepted Submission(s): 96

Problem Description

Kingdom Y is in the war with kingdom X. Kingdom X consists of N cities,there are N-1 bidirectional roads which are all 1 long ，each of them connect a pair of cities,the N cities are all connect by the N-1 bidirectional.People can travel through the roads.

Now kingdom Y is going to bomb kingdom X. Every city of kingdom X has its own value W. If city i was to be bombed, then all the cities that lie within the distance W(i) from city i would be destroyed as well. The king of kingdom Y wants to know the minimum bombing time that can destroy all the cities in kingdom X. Could you help him?

Input

There are multiple test cases. Please process till EOF.
In each test case:
First line: an integer n(n<=10^5) indicating the number of city
Second line:contain n numbers w[i](0<=w[i]<=100) ,indicating that the value of city[i],
Next n - 1 lines: each contains two numbers ui and vi, (1 ≤ ui,vi<=n), indicates that there’s one road connecting city ui and vi.

Output

For each case,output one number, denotes the minimum number of bombing times.

Sample Input

1 1 1 1 1

1 2

2 3

3 4

4 5

Sample Output

Author

FZUACM

Source

2015 Multi-University Training Contest 1

解题：dp

令F[i][j]为以i为根的子树，能向子树外拓展j个节点最少需要炸毁几个城市。G[i][j]为以i为根的子树，子树内有节点未被炸毁，且距离根为j最少需要炸毁几个城市。
转移方程:
不炸毁u点

$F[u][j] = F[v][j+1] + min(F[k][0dots j+1,G[k][0dots j])$

$G[u][0] = F[u][0]$

$G[u][j] = G[v][j-1] + min(F[k][0dots j-1],G[k][0dots j-1])$

炸毁u点

$F[u][w[u]] = 1 + min(F[v][0dots w[u]+1],G[v][w[u]])$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 100010;
  4 struct arc {
  5     int to,next;
  6     arc(int x = 0,int y = -1) {
  7         to = x;
  8         next = y;
  9     }
 10 } e[maxn<<1];
 11 int head[maxn],d[maxn],n,tot;
 12 void add(int u,int v) {
 13     e[tot] = arc(v,head[u]);
 14     head[u] = tot++;
 15     e[tot] = arc(u,head[v]);
 16     head[v] = tot++;
 17 }
 18 int q[maxn],p[maxn],de[maxn],hd,tl;
 19 int F[maxn][110],G[maxn][110],A[maxn][110],B[maxn][110];
 20 int main() {
 21     int u,v,a,b;
 22     while(~scanf("%d",&n)) {
 23         for(int i = 1; i <= n; ++i)
 24             scanf("%d",d+i);
 25         tot = 0;
 26         memset(head,-1,sizeof head);
 27         memset(G,-1,sizeof G);
 28         memset(F,-1,sizeof F);
 29         memset(A,-1,sizeof A);
 30         memset(B,-1,sizeof B);
 31         for(int i = 1; i < n; ++i) {
 32             scanf("%d%d",&u,&v);
 33             add(u,v);
 34         }
 35         p[q[hd = tl = 0] = 1] = -1;
 36         while(hd <= tl) {
 37             de[u = q[hd++]] = 0;
 38             for(int i = head[u]; ~i; i = e[i].next) {
 39                 if(e[i].to != p[u]) {
 40                     p[e[i].to] = u;
 41                     q[++tl] = e[i].to;
 42                 }
 43             }
 44         }
 45         while(tl >= 0) {
 46             v = q[tl--];
 47             if(p[v] >= 0) de[p[v]] = max(de[p[v]],de[v]+1);
 48             if(!de[v]) {
 49                 if(d[v] >= 0) {
 50                     F[v][d[v]] = 1;
 51                     for(int i = 0; i < d[v]; ++i) A[v][i] = -1;
 52                     for(int i = d[v]; i < 101; ++i) A[v][i] = 1;
 53                 }
 54                 G[v][0] = 0;
 55                 for(int i = 0; i <= 100; ++i) B[v][i] = 0;
 56                 continue;
 57             }
 58 
 59             for(int i = 0; i <= min(100,de[v]); ++i) {
 60                 G[v][i] = 0;
 61                 for(int j = head[v]; ~j; j = e[j].next) {
 62                     u = e[j].to;
 63                     if(u == p[v]) continue;
 64                     a = B[u][i-1];
 65                     b = A[u][100];
 66                     if(a == -1 && b == -1) {
 67                         G[v][i] = -1;
 68                         break;
 69                     }
 70                     if(a == -1) a = maxn;
 71                     if(b == -1) b = maxn;
 72                     G[v][i] += min(a,b);
 73                 }
 74                 if(G[v][i] == -1) break;
 75             }
 76 
 77 
 78             if(d[v] >= 0) {
 79                 F[v][d[v]] = 1;
 80                 for(int i = head[v]; ~i; i = e[i].next) {
 81                     u = e[i].to;
 82                     if(u == p[v]) continue;
 83                     a = A[u][100];
 84                     b = -1;
 85                     if(d[v] > 0) b = B[u][d[v]-1];
 86                     if(a == -1 && b == -1) {
 87                         F[v][d[v]] = -1;
 88                         break;
 89                     }
 90                     if(a == -1) a = maxn;
 91                     if(b == -1) b = maxn;
 92                     F[v][d[v]] += min(a,b);
 93                 }
 94             }
 95 
 96             for(int i = head[v]; ~i; i = e[i].next) {
 97                 u = e[i].to;
 98                 if(u == p[v]) continue;
 99                 for(int j = 1; j <= 100; ++j)
100                     if(F[u][j] != -1) {
101                         int tmp = 0;
102                         for(int k = head[v]; ~k; k = e[k].next) {
103                             if(e[k].to != u && e[k].to != p[v]) {
104                                 a = A[e[k].to][100];
105                                 b = -1;
106                                 if(j - 2 >= 0) b = B[e[k].to][j-2];
107                                 if(a == -1 && b == -1) {
108                                     tmp = -1;
109                                     break;
110                                 }
111                                 if(a == -1) a = maxn;
112                                 if(b == -1) b = maxn;
113                                 tmp += min(a,b);
114                             }
115                         }
116                         if(tmp != -1 && (F[v][j-1] == -1 || F[v][j-1] > F[u][j] + tmp))
117                             F[v][j-1] = F[u][j] + tmp;
118                     }
119             }
120             A[v][0] = F[v][0];
121             B[v][0] = G[v][0];
122             for(int i = 1; i <= 100; ++i) {
123                 A[v][i] = A[v][i-1];
124                 if(F[v][i] != -1 && (A[v][i] == -1 || A[v][i] > F[v][i]))
125                     A[v][i] = F[v][i];
126                 B[v][i] = B[v][i-1];
127                 if(G[v][i] != -1 && (B[v][i] == -1 || B[v][i] > G[v][i]))
128                     B[v][i] = G[v][i];
129             }
130         }
131         int ret = -1;
132         for(int i = 0; i <= 100; ++i)
133             if(F[1][i] != -1 && (ret == -1 || ret > F[1][i]))
134                 ret = F[1][i];
135         printf("%d
",ret);
136     }
137     return 0;
138 }
139 /*
140 5
141 1 1 1 1 1
142 1 2
143 2 3
144 3 4
145 4 5
146 */

View Code