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;
}