链接: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;
}