P2899 树图染色信号覆盖树形DP

博主：枫亚
发布时间：2022 年 03 月 26 日
640 次浏览
暂无评论
4907字数
分类：

## 抄题

### 题目描述

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

John想让他的所有牛用上手机以便相互交流(也是醉了。。。)，他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地能收到信号。给你N-1个草地(A，B)的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。

### 输入格式

Line 1: A single integer: N

Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

### 输出格式

* Line 1: A single integer indicating the minimum number of towers to install
* 
### 输入输出样例

#### 输入 #1
```
5
1 3
5 2
4 3
3 5
```
#### 输出 #1
```
2
```

## 解析

`n`个点，`n-1`条边，可知图为树。

任意定根，树等价。

子问题：在给定的子树上填色（布置信号塔），使得子树中完成信号覆盖。

子情况：

1. 子树根的信号覆盖由自身提供。（此时子树根的子节点仍可以被填色）
2. 子树根的信号覆盖由儿子提供。（此时子树根仍可以被填色）
3. 子树根的信号覆盖由父亲提供。（此时子树根与其子节点仍可以被填色）。

取数组`f[point_total][3]`，

使得：

1. `f[root][0]`存放`子树根信号由其自身提供`时`该子树中最少需要布置的信号塔数量`。
2. `f[root][1]`存放`子树根信号由其儿子提供`时`该子树中最少需要布置的信号塔数量`。
3. `f[root][2]`存放`子树根信号由其父亲提供`时`该子树中最少需要布置的信号塔数量`。

对于这三种情况而言：

当子树根信号由其自身提供时，子树根的子节点可以取`0-2`三种情况，因为对于任意一种情况子节点都有着信号覆盖。子树中信号塔数量为（别忘了树根自身的1）：

$$f[root][0] = 1 + \sum_{son}\left(\min\left(f[son][0], f[son][1], f[son][2]\right)\right)$$

当子树根信号由其儿子提供时，其中必须有至少一个儿子经过染色（有信号塔）。

此时对于这个儿子而言自身必须填色，其他儿子可以选择自己是否填色。对于所有而言，父亲节点都没有规定“一定被填色”，所以不能以f[v][2]考虑最小值情况（根节点可以不被填色）。

$$f[root][1] = \min_{best\_son} \left( f[best\_son][0] + \sum_{v\in other\_sons} (f[v][0], f[v][1])\right)$$

当子树根信号由其父亲提供时，子树根不需要被填色。子树根的子节点可以由子节点的儿子提供信号，也可以由子节点自身提供信号，但是不能被子树根提供信号。

所以有

$$f[root][2] = \sum_{son} \min(f[son][0], f[son][1])$$

## 优化

注意到：

`f[root][1]`的暴力求解需要遍历所有儿子，还要求和，这是不好的（没有尝试去计算这东西的复杂度，但它一定是坏的）。

又注意到：

`f[root][2]`的结果可以被`f[root][1]`使用。

且

$$f[root][1] = f[root][2] + f[best\_son][0] - min(f[best\_son][0], f[best\_son][1])$$

其中`best_son`需要使$f[best\_son][0] - min(f[best\_son][0], f[best\_son][1])$尽可能小。

所以可以这么做：

在遍历所有节点时记录下使得$f[best\_son][0] - min(f[best\_son][0], f[best\_son][1])$尽可能小的best_son节点序号，

在遍历完成之后只需$O(1)$即可根据$f[best\_son][2]$求出$f[best\_son][1]$。

## 实现

### 存图

链式前向星存图，需要维护以下数据结构：

```c++
typedef struct Edge
{
    int next_edge;
    int lead_to;
} Edge;

Edge edge_pool[maxn];
int now_new_edge = 1;
int first_edge[maxn];
```

即，存每一个节点的“第一条边”在“边存储内存池”中的位置，对于每一条边来说，除了存储这条边的指向节点外，还存储下一条边在“边存储内存池”中的位置。

每个节点最后一条边的下一条边为0号空边。

注意：每一条边均为有向边，存无向图的无向边时需要添加正反两条边。

```c++
void add_edge(int u, int v)
{
    Edge temp;
    temp.next_edge = first_edge[u];     // 向链表头加新的边节点
    temp.lead_to = v;
    first_edge[u] = now_new_edge;
    edge_pool[now_new_edge] = temp;
    now_new_edge++;
}
```

### 遍历

```c++
void dfs(int root, int father)
{
    // do something
    for(int edge_index = first_edge[root]; edge_index != 0; edge_index = edge_pool[edge_index].next_edge)
    {
        int v = edge_pool[index_e].lead_to;
        if (v == father)    // 找到了当前根向上回溯父节点的边
            continue;       // 忽略向上边
        // do something
        dfs(v, root);
        // do something
    }
    // do something
}
```

## AC代码

```c++
#include <iostream>

using namespace std;

const int maxn = 100000;

const int inf = 2e9+5;

#define int long long

typedef struct Edge
{
    int next_edge;
    int lead_to;
} Edge;

Edge edge_pool[maxn];
int now_new_edge = 1;
int first_edge[maxn];

int f[maxn][3];

void add_edge(int u, int v)
{
    Edge temp;
    temp.next_edge = first_edge[u];
    temp.lead_to = v;
    first_edge[u] = now_new_edge;
    edge_pool[now_new_edge] = temp;
    now_new_edge++;
}

void dfs(int u, int father)
{
    int best_son = 0;
    f[u][0] = 1;
    for (int index_e = first_edge[u]; index_e != 0; index_e = edge_pool[index_e].next_edge)
    {
        int v = edge_pool[index_e].lead_to; // one son
        if (v == father)
            continue;
        dfs(v, u);
        f[u][0] += min(min(f[v][0], f[v][1]), f[v][2]);
        f[u][2] += min(f[v][0], f[v][1]);
        if(f[v][0]-min(f[v][0], f[v][1]) < f[best_son][0] - min(f[best_son][0], f[best_son][1]))
        {
            best_son = v;
        }
    }
    f[u][1] = f[u][2] - min(f[best_son][0], f[best_son][1]) + f[best_son][0];
}

signed main()
{
    int N;
    int u, v;
    cin >> N;
    while (N-- > 1)
    {
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    f[0][0] = inf;      // best_son must be better than 0, and if no son, than min(inf, f[0][1]) = 0.
    dfs(1, 0);
    cout << min(f[1][0], f[1][1]) << endl;          // no f[1][2], because root has no father.
    return 0;
}
```

最后修改：2022 年 03 月 26 日

如果觉得这篇文章对你有用，请随意赞赏~

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

ssf
看不到内容啊。
潜龙于渊
完美解决问题！感谢大佬！
123
感谢，配置成功
WetABQ
啊这（那可能，可能... 可能不是吧我是因为 Gyrojeff...
WetABQ
ADHD 大概率下是被迫的，几乎任何情况下都无法集中精力「对于...

MA366-Ch1
评论数： 0
CSAPP-20210903
评论数： 0
梦想 - 看完白箱有感
评论数： 0
PH380-Cours1
评论数： 0
P5076 二叉搜索树（未优化）
评论数： 0

P2899 树图染色信号覆盖树形DP

枫亚 • 2022 年 03 月 26 日

## 抄题

### 题目描述

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

### 输入格式

Line 1: A single integer: N

Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

### 输出格式

* Line 1: A single integer indicating the minimum number of towers to install
* 
### 输入输出样例

#### 输入 #1
```
5
1 3
5 2
4 3
3 5
```
#### 输出 #1
```
2
```

## 解析

`n`个点，`n-1`条边，可知图为树。

任意定根，树等价。

子问题：在给定的子树上填色（布置信号塔），使得子树中完成信号覆盖。

子情况：

取数组`f[point_total][3]`，

使得：

对于这三种情况而言：

$$f[root][0] = 1 + \sum_{son}\left(\min\left(f[son][0], f[son][1], f[son][2]\right)\right)$$

当子树根信号由其儿子提供时，其中必须有至少一个儿子经过染色（有信号塔）。

$$f[root][1] = \min_{best\_son} \left( f[best\_son][0] + \sum_{v\in other\_sons} (f[v][0], f[v][1])\right)$$

所以有

$$f[root][2] = \sum_{son} \min(f[son][0], f[son][1])$$

## 优化

注意到：

`f[root][1]`的暴力求解需要遍历所有儿子，还要求和，这是不好的（没有尝试去计算这东西的复杂度，但它一定是坏的）。

又注意到：

`f[root][2]`的结果可以被`f[root][1]`使用。

且

$$f[root][1] = f[root][2] + f[best\_son][0] - min(f[best\_son][0], f[best\_son][1])$$

其中`best_son`需要使$f[best\_son][0] - min(f[best\_son][0], f[best\_son][1])$尽可能小。

所以可以这么做：

在遍历所有节点时记录下使得$f[best\_son][0] - min(f[best\_son][0], f[best\_son][1])$尽可能小的best_son节点序号，

在遍历完成之后只需$O(1)$即可根据$f[best\_son][2]$求出$f[best\_son][1]$。

## 实现

### 存图

链式前向星存图，需要维护以下数据结构：

```c++
typedef struct Edge
{
    int next_edge;
    int lead_to;
} Edge;

Edge edge_pool[maxn];
int now_new_edge = 1;
int first_edge[maxn];
```

每个节点最后一条边的下一条边为0号空边。

注意：每一条边均为有向边，存无向图的无向边时需要添加正反两条边。

### 遍历

## AC代码

```c++
#include <iostream>

using namespace std;

const int maxn = 100000;

const int inf = 2e9+5;

#define int long long

typedef struct Edge
{
    int next_edge;
    int lead_to;
} Edge;

Edge edge_pool[maxn];
int now_new_edge = 1;
int first_edge[maxn];

int f[maxn][3];

void add_edge(int u, int v)
{
    Edge temp;
    temp.next_edge = first_edge[u];
    temp.lead_to = v;
    first_edge[u] = now_new_edge;
    edge_pool[now_new_edge] = temp;
    now_new_edge++;
}

P2899 树图染色信号覆盖树形DP

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Ubuntu环境下iBus-Rime小鹤双拼音形方案配置记录

死要面子活受罪

对学习焦虑的思考

茶铺开张啦

学习方法探索 - 1

MA366-Ch1

CSAPP-20210903

梦想 - 看完白箱有感

PH380-Cours1

P5076 二叉搜索树（未优化）

P2899 树图染色信号覆盖树形DP

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

P2899 树图染色信号覆盖 树形DP

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

P2899 树图染色信号覆盖树形DP