首页 > 代码库 > HLG1477战争与守卫【树形dp】

HLG1477战争与守卫【树形dp】

2024-08-07 11:29:24   229人阅读

Description

J国和C国爆发了战争，J国派出了很多间谍深入到C国内部，经常在C国的城市之间炸毁道路，阻拦C国的军队，C国为了抓到这些间谍，需要派人在城市进行监视，一个城市只要有一个人监视，那么这个城市的所有的道路也都会被监视到，为了能够尽量多的士兵去前线打仗，监视的士兵要尽可能的少，希望靠你编程求出至少需要多少人能实现对所有城市之间道路的监视。

Input

有多组测试数据

每组测试数据的第一行，一个整数n表示C国城市的数量(编号为0-----n-1) n<=2000

接下来n行：i:(M)表示有M个城市和城市i之间有道路连通，然后是M个整数表示和i连通的城市的编号。

处理到文件结束，输入数据保证是一棵树。

Output

输出一个整数，表示至少需要多少士兵能实现对所有道路的监视。

Sample Input

4

0:(1) 1

1:(2) 2 3

2:(0)

3:(0)

Sample Output
1
Source
Southeastern Europe 2000

 

分析：这个题跟上一个很像

dp[x][0]表示x为根节点的树不选x点并且把所有的点都覆盖的的最少士兵
dp[x][1]表示x为根节点的树选x点并且把所有的点都覆盖的的最少士兵

dp[x][0] = sum(dp[y][1]) + 1

dp[x][1] = sum(min(dp[y][0], dp[y][1]))

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 2005; 7 int dp[maxn][2]; 8 int n; 9 int in[maxn], out[maxn];10 struct Node {11     int to, next;12 }e[maxn * maxn];13 int tot;14 int head[maxn];15 void add(int u, int v) {16     e[tot].to = v;17     e[tot].next = head[u];18     head[u] = tot++;19 }20 int boss;21 22 void dfs(int u) {23     if(out[u] == 0) {24         dp[u][0] = 0;25         dp[u][1] = 1;26         return ;27     }28     int sum1 = 0; int sum2 = 0;29     for(int i = head[u]; i; i = e[i].next) {30         int v = e[i].to;31         dfs(v);32         sum1 += dp[v][1];33         sum2 += min(dp[v][0], dp[v][1]);34     }35     dp[u][0] = sum1;36     dp[u][1] = sum2 + 1;37 }38 39 int DP() {40     memset(dp, 0, sizeof(dp));41     dfs(boss);42     return min(dp[boss][0], dp[boss][1]);43 }44 45 int main() {46     int u, m, v;47     while(EOF != scanf("%d",&n) ) {48         memset(in, 0, sizeof(in));49         memset(out, 0, sizeof(out));50         memset(head, 0, sizeof(head));51         tot = 1;52         for(int i = 1; i <= n; i++) {53             scanf("%d:(%d)", &u, &m);54             for(int j = 1; j <= m; j++) {55                 scanf("%d",&v);56                 add(u, v);57                 out[u]++; in[v]++;58             }59         }60         for(int i = 0; i < n; i++) {61             if(in[i] == 0) {62                 boss = i;63                 break;64             }65         }66         printf("%d\n", DP());67     }68     return 0;69 }
View Code

 

HLG1477战争与守卫【树形dp】


联系
我们