Rinne Loves Edges (树形dp之删边)

链接:https://ac.nowcoder.com/acm/contest/370/F
来源:牛客网
 

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

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↔3是最优的。

备注:

2≤S≤N≤10^5 ,M=N−1,保证答案在 C++ long long 范围内。

题意:删除价值和最少的边,使得叶子节点不能连接到重要点~

题解:树形dp,小菜鸡的我知道怎么做,但是写起来好难啊,特别是邻接表一直不是很懂~~,此题就是枚举路径上的边,找最小的,然后求和~即:dp[u]+=min(dp[vv],ww),详细请看代码~

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int MAX = 1e6+20;
struct hh{
	int u,v;
	ll w;
	int nt;
}a[MAX];
int tot,n,m,s;
int head[MAX];
ll dp[MAX];
void add(int u,int v,ll w){//邻接表,建图
	a[tot].v=v;
	a[tot].w=w;
	a[tot].nt=head[u];
	head[u]=tot++;
}
void dfs(int u,int pre){
	if(a[head[u]].nt==-1&&a[head[u]].v==pre){//重要点的位置初始化为无穷大
		dp[u]=inf;
		return;
	}
	for (int i = head[u]; ~i; i = a[i].nt){
		int vv=a[i].v;
		ll ww=a[i].w;
		if(vv^pre){
			dfs(vv,u);
			dp[u]+=min(dp[vv],ww);//状态转移,枚举路径上的边,找最小的,然后求和
		}
	}
}
int main(){
	cin >> n >> m >> s;
	memset(head,-1,sizeof(head));
	while(m--){
		int u,v;
		ll w;
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs(s,0);
	cout << dp[s] << endl;
	return 0;
}

 

全部评论

相关推荐

06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务