洛谷P1269 信号放大器 题解

题目链接：P1269 信号放大器

题意：

树型网络是最节省材料的网络。所谓树型网络，是指一个无环的连通网络，网络中任意两个结点间有且仅有一条通信道路。

网络中有一个结点是服务器，负责将信号直接或间接地发送到各终端机。如图上方，server结点发出一个信号给结点 $a$ 和 $c$ ，$a$ 再转发给 $b$ 。如此，整个网络都收到这个信号了。

但是，实际操作中，信号从一个结点发到另一个结点，会出现信号强度的衰减。衰减量一般由线路长度决定。

如图下方，边上所标的数字为边的衰减量。假设从server出发一个强度为 $4$ 个单位的信号，发到结点a后强度衰减为 $4-3=1$ 个单位。结点 $a$ 再将其转发给结点 $b$ 。由于信号强度为 $1$ ，衰减量为 $2$ ，因此信号无法发送到 $b$ 。

一个解决这一问题的方法是，安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度（从服务器出发时的强度）。

上图中，若在结点 $a$ 处安装一个信号放大器，则强度为 $4$ 的信号发到 $a$ 处，即被放大至 $4$ 。这样，信号就可以被发送的网络中的任意一个节点了。为了简化问题，我们假定每个结点只处理一次信号，当它第二次收到某个信号时，就忽略此信号。

你的任务是根据给出的树型网络，计算出最少需要安装的信号放大器数量。

输入格式：

第一行一个整数 $n ~(n \le 2\times 10^4)$，表示网络中结点的数量。

第 $2\sim n+1$ 行，每行描述一个节点的连接关系。其中第 $i+1$ 行，描述的是结点 $i$ 的连接关系：首先一个整数 $k$ ，表示与结点 $i$ 相连的结点的数量。此后 $2k$ 个数，每两个描述一个与结点 $i$ 相连的结点，分别表示结点的编号（编号在 $1\sim n$ 之间）和该结点与结点 $i$ 之间的边的信号衰减量。结点 $1$ 表示服务器。

最后一行，一个整数，表示从服务器上出发信号的强度。

输出格式：

一个整数，表示要使信号能够传遍整个网络，需要安装的最少的信号放大器数量。

如果不论如何安装信号放大器，都无法使信号传遍整个网络，则输出No solution.

考虑贪心。

按深度从大到小依次考虑每个结点。

如果 $u$ 连的某个结点 $v$ 所在子树没法全部传递成功，则在 $u$ 放一个

正确性显然。因为如果你不放， $v$ 的子树一定传递不了。

而我们是从下往上递归处理的，根据数学归纳法，显然正确

注意这道题信号强度为 $0$ 时也是可以传递信息的。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e4+15))

int n,m,ans,pos=1,head[N],pre[N],dis[N];
struct Edge{int u,v,w,next;}e[N*2];
void addEdge(int u,int v,int w)
{ e[++pos]={u,v,w,head[u]}; head[u]=pos; }
void dfs(int u,int f)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; if(v == f) continue;
        pre[v] = e[i].w;
        dfs(v,u); up(dis[u], dis[v] + e[i].w);
    }
    if(dis[u] + pre[u] >= m) dis[u]=0,++ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; int mx=-1;
    for(int u=1,cnt,v,w; u<=n; u++)
    {
        cin >> cnt;
        for(int i=1; i<=cnt; i++)
        { cin >> v >> w; addEdge(u,v,w); up(mx,w); }
    }
    cin >> m; if(mx >= m) return cout << "No solution.\n",0;
    dfs(1,1); cout << ans << '\n';
    return 0;
}

---

一开始我在题目给的双向边的基础上又建了双向边，然后挂了。。。（属于眼瞎的。）

WA倒是很正常，但是TLE是我百思不得其解的。改动如下（数组我开大了，所以不是越界问题）

for(int i=1; i<=cnt; i++)
{ cin >> v >> w; addEdge(u,v,w); addEdge(v,u,w); up(mx,w); }

感谢Roundgod老师的再次帮助 Orz

因为这样建图之后，我的代码会把每个点跑 $2$ 遍，所以复杂度会飙升到指数级。

比如某个结点跑了 $2$ 次，那它的每个子结点每次都会跑 $2$ 次，则每个子结点会跑 $4$ 次。

因此它子树最深的结点（记深度为 $d$ ）会跑 $\mathcal{O}(2^d)$ 次，显然会超时。所以其实不是有环的问题。