uva 10859 Placing Lampposts

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:支配问题,无根树,在一个点被选后可以覆盖与它直接相连的所有边,问要覆盖所有树边,最少的点数,在保证了点数最少后,令到一些边被两个点可能覆盖的数目又最多。最后输出最少点数,被2个点同时覆盖的最多边数,被1条点覆盖的边数。注意是森林不是树。

比较简单的题目了

dp[u][0],dp[u][1],不选点u和选点u,u子树下的边都被覆盖的需要的最少点数

num[u][0],num[u][1],表示对应上面的状态,同时被2个点覆盖的边数的最大值

dp[u][0] = sigma dp[v][1]; num[u][0] = sigma num[v][1];

dp[u][1] = sigma min(dp[v][1],dp[v][0]);

if(dp[v][1] < dp[v][0]) num[u][1] += (num[v][1]+1);

else if(dp[v][0] < dp[v][1]) num[u][1] += num[v][0];

else if(dp[v][0] == dp[v][1]) num[u][1] += max(num[v][1]+1 , num[v][0]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1010
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n;
vector<int>e[N];
int dp[N][2],num[N][2];
bool vis[N];

void dfs(int u){
vis[u] = true;
dp[u][0] = dp[u][1] = 0;
num[u][0] = num[u][1] = 0;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(vis[v]) continue;
dfs(v);
dp[u][0] += dp[v][1];
num[u][0] += num[v][1];
if(dp[v][0] < dp[v][1]){
dp[u][1] += dp[v][0]; num[u][1] += num[v][0];
}
else if(dp[v][1] < dp[v][0]){
dp[u][1] += dp[v][1]; num[u][1] += (num[v][1]+1);
}
else{
dp[u][1] += dp[v][1];
num[u][1] += max(num[v][1]+1,num[v][0]);
}
}
dp[u][1]++;
}

int main(){
int T,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 0; i <= n; i++)
e[i].clear();
for(int i = 0; i < m; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
int res = 0,cnt = 0;
cl(vis,false);
for(int i = 0; i < n; i++)
if(!vis[i]){
dfs(i);
if(dp[i][0] < dp[i][1]){
res += dp[i][0];
cnt += num[i][0];
}
else if(dp[i][1] < dp[i][0]){
res += dp[i][1];
cnt += num[i][1];
}
else{
res += dp[i][1];
cnt += max(num[i][0] , num[i][1]);
}
}
printf("%d %d %d\n",res,cnt,m-cnt);
}
return 0;
}