当前位置:   article > 正文

刷题记录:牛客NC22598Rinne Loves Edges

刷题记录:牛客NC22598Rinne Loves Edges

传送门:牛客

题目描述:

Rinne  最近了解了如何快速维护可支持插入边删除边的图,并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图,每条边有一个边权 wi
现在她想玩一个游戏:选取一个 “重要点” S,然后选择性删除一些边,使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权,现在 Rinne 想知道完成这个游戏的最小的代价,这样她就能轻松到达 rk1 了!作为回报,她会让你的排名上升一定的数量。
输入:
4 3 1 
1 2 1 
1 3 1 
1 4 1
输出:
1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

一道简单经典的树形dp的题目.

主要思路:

  1. 首先这道题有一个很重要的信息在备注里,那里描述了 m = n − 1 m=n-1 m=n1,而作为一个联通图加上这个性质,那么这个联通图将变成一颗树!!,然后我们就可以使用树上的算法了
  2. 首先先使用一个 d p [ u ] dp[u] dp[u]数组来存储 u u u节点与所有其子树中的叶子节点断开的最小代价.然后我们不难想到这样的一个转移的想法: 那就是当前结点要是想要与自己的所有叶子节点断开关系的话,要么与当前的儿子断开关系,断开当前的儿子(也就是叶子节点的父亲),显然就是直接断开了所有的叶子节点了,或者不选择断开儿子,选择断开所有的叶子节点,然后从这两种情况下选择一种花费比较少的就行.

d p [ u ] = m i n ( d p [ v ] , d f s ( v ) ) dp[u]=min(dp[v],dfs(v)) dp[u]=min(dp[v],dfs(v))

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m,s;
struct Node{
	ll v,w;
};
vector<Node>tree[maxn];
ll dp[100010];
ll dfs(int u,int pre_u) {
	if(tree[u].size()==1&&u!=s) return ll_maxn;
	for(int i=0;i<tree[u].size();i++) {
		Node to=tree[u][i];
		if(to.v==pre_u) continue;
		dp[u]+=min(to.w,dfs(to.v,u));
	}
	return dp[u];
}
int main() {
	n=read();m=read();s=read();
	int u,v,w;
	for(int i=1;i<=m;i++) {
		u=read();v=read();w=read();
		tree[u].push_back({v,w});
		tree[v].push_back({u,w});
	}
	dfs(s,-1);
	cout<<dp[s]<<endl;
	return 0;
}
  • 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
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/blog/article/detail/52864
推荐阅读
相关标签
  

闽ICP备14008679号