洛谷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)\) 次，显然会超时。所以其实不是有环的问题。