【每日一题】Rinne Loves Edges
Rinne Loves Edges
https://ac.nowcoder.com/acm/problem/22598
题目
题目描述：Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 wi。
现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。
输入描述：
第一行三个整数 N,M,S，意义如「题目描述」所述。
接下来 M 行，每行三个整数 u,v,w 代表点 u 到点 v 之间有一条长度为 w 的无向边。
一个整数表示答案。
解析
这道题是一道简单的树形dp，只是我对树形dp（实则是对dp）不太熟，所以没想到求解方法。
- 所以开头还是那句话：动态规划的基础就是递推。
树形dp：
- 想要求解这道题，我们先要读懂题目的意思：我们要用最少的代价，使得当前根节点和所有叶子节点不相连（看题很重要，一开始我没发现是树）。
- 然后到这里，我们就要想一下该怎么递推，该怎么把大问题分解成等同的小问题（我就是在这卡到了）。
- 所有在这里，根据我们要做的事情：断开节点：我们应该想到以某一u（节点）为根节点的树对一条分支有两种断开方法。
<1>断开自己和某一v（子节点）之间的关系。<2>断开子节点v的所有子节点（一定是断开所有子节点，因为树的每一条分支最终一定以叶节点结束）。 - 所以我们就能得到转移方程：
（w表示u到某一分支的权值）。
- 补充一句邓老师告诉我的话：树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。
打代码哦：
- 前向星保存树形关系。
- dfs进行优先遍历。（上面树形dp讲了详细方法）
- 其他重要的就是一点点操作顺序了吧，看代码~
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
//代码预处理区
const int INF = 0x3f3f3f3f;
const int MAX = 1e5 + 7;
int head[MAX], tot;
struct Node {
int v, w, next;
} edge[MAX << 1];
ll f[MAX];
//全局变量区
template<class T>inline void read(T& res);
void add_edge(int u, int v, int w);
void dfs(int u, int fa);
//函数预定义区
int main() {
int N, M, S; read(N); read(M); read(S);
tot = 0; memset(head, 0, sizeof head);
for (int i = 1; i <= M; i++) {
int u, v, w; read(u); read(v); read(w);
add_edge(u, v, w);
add_edge(v, u, w);
}
memset(f, 0, sizeof f);
dfs(S, 0);
printf("%lld", f[S]);
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
void add_edge(int u, int v, int w) {
tot++;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
int flag = 0;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
int w = edge[i].w;
if (fa == v) continue;
flag = 1;
dfs(v, u);
f[u] += min(f[v], (ll)w);
}
if (!flag) f[u] = INF;
}
//函数区 每日一题 文章被收录于专栏
憨憨的专栏
海康威视工作强度 84人发布
投递理想汽车等公司10个岗位 >
