Rinne Loves Edges
题目描述
Rinne 最近了解了如何快速维护可支持插入边删除边的图, 并且高效的回答一下奇妙的询问.
她现在拿到了一个 n 个节点 m 条边的无向连通图, 每条边有一个边权
wiwi
现在她想玩一个游戏: 选取一个 "重要点" S, 然后选择性删除一些边, 使得原图中所有除 S 之外度为 1 的点都不能到达 S.
定义删除一条边的代价为这条边的边权, 现在 Rinne 想知道完成这个游戏的最小的代价, 这样她就能轻松到达 rk1 了! 作为回报, 她会让你的排名上升一定的数量.
输入描述:
第一行三个整数 N,M,S, 意义如「题目描述」所述.
接下来 M 行, 每行三个整数 u,v,w 代表点 u 到点 v 之间有一条长度为 w 的无向边.
输出描述:
一个整数表示答案.
示例 1
输入
- 4 3 1
- 1 2 1
- 1 3 1
- 1 4 1
输出
3
说明
需要使得点 2,3,4 不能到达点 1, 显然只能删除所有的边, 答案为 3
示例 2
输入
- 4 3 1
- 1 2 3
- 2 3 1
- 3 4 2
输出
1
说明
需要使得点 4 不能到达点 1, 显然删除边 2?32?3 是最优的.
备注:
2≤S≤N≤105,M=N?1, 保证答案在 C++ long long 范围内.
题解:
通过数据范围 n = m-1 不难发现这是一棵树, 注意到树上只有根和叶子的度可能为 1.
于是题目转变求为了一棵根为 S 的树, 选择性切掉一些边, 使得所有的叶子都不能到达根的最小代价.
让我们考虑树形 dp(其实可能就是个统计算不上 dp): 设 fv 表示使得以 v 为根的子树内的叶子到不了 v 的最小代价, 转移显然枚举每一条边切不切就可以了.
方程大概是这样: 设当前我们要更新的点是 u,u 的一个儿子是 v, 他们之间的边的边权是 w. 则有转移方程 fu+=min{fv,w}
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5+10;
- ll in[maxn];
- ll n,m,s,u,v,w;
- struct node{
- ll to;
- ll val;
- }head,tail;
- vector<node>g[maxn];
- ll dfs(ll pos,ll res,ll root){
- ll ans=0;
- for(int i=0;i<g[pos].size();i++){
- head=g[pos][i];
- int to=head.to;
- if(to==root)
- continue;
- else if(in[to]==1){
- ans+=head.val;
- }
- else{
- ans+=dfs(to,head.val,pos);
- }
- }
- return min(ans,res);
- }
- int main()
- {
- cin>>n>>m>>s;
- for(int i=0;i<m;i++){
- scanf("%lld %lld %lld",&u,&v,&w);
- head.to=v;
- head.val=w;
- g[u].push_back(head);
- head.to=u;
- g[v].push_back(head);
- in[u]++;
- in[v]++;
- }
- ll ans=0;
- for(int i=0;i<g[s].size();i++){
- node tmp=g[s][i];
- if(in[tmp.to]==1){
- ans+=tmp.val;
- }
- else{
- ans+=dfs(tmp.to,tmp.val,s);
- }
- }
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2950891.html