题目链接
Solution
这题目很坑,把重要的信息放在了最后面,即$M=N-1$,而且还是一个无向连通图。。除了输入N还要输入M不知道意义何在
题目转换一下即要使原来的除了S以外的叶子节点全部都不能和S连通。
显然我们需要以$S$点作为根节点,然后才好做。
令$dp[u]$代表令节点$u$的子树的叶子节点均到达不了节点$u$。那么就有
$$
dp[u]=\begin{cases}
inf,&u\text{是叶子节点}\
\sum\limits_{v,w\in \text{u的子节点}}{min(dp[v],w)},&u\text{不是叶子节点}
\end{cases}
$$
当$u$是叶子节点的时候,他无法完成这样的操作,所以$dp[u]$为$\infty$。
当$u$不是叶子节点的时候,对于它的儿子而言,要么删掉到它的儿子的这一条边,要么使用它的儿子就可以做到的最好的情况。这两种情况做一个比较选择最优的方案即可。
时间复杂度$O(n)$ 空间复杂度$O(n)$
Code
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
| #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10;
struct edge { int v; ll w; int nxt; } G[N << 1]; int h[N], tot;
void addedge(int u, int v, ll w) { G[tot] = {v, w, h[u]}; h[u] = tot++; G[tot] = {u, w, h[v]}; h[v] = tot++; } ll dp[N]; void dfs(int u, int f) { bool isLeaf = true; for(int i = h[u]; ~i; i = G[i].nxt) { const int v = G[i].v; if(v != f) { isLeaf = false; dfs(v, u); dp[u] += min(dp[v], G[i].w); } } if(isLeaf) dp[u] = LLONG_MAX; } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); memset(h, 0xff, sizeof h); tot = 0; int n, m, s; cin >> n >> m >> s; for(int i = 0; i < m; i++) { int u, v; ll w; cin >> u >> v >> w; addedge(u, v, w); } dfs(s, -1); cout << dp[s] << '\n'; }
|
回到开头