抄题

题目描述

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]$。

实现

存图

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

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

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

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

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

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

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 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代码

#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 日 02 : 31 PM
如果觉得这篇文章对你有用,请随意赞赏~