赞
踩
传送门:牛客
题目描述:
Rinne 最近了解了如何快速维护可支持插入边删除边的图,并且高效的回答一下奇妙的询问。
她现在拿到了一个 n 个节点 m 条边的无向连通图,每条边有一个边权 wi
现在她想玩一个游戏:选取一个 “重要点” S,然后选择性删除一些边,使得原图中所有除 S 之外度为 1 的点都不能到达 S。
定义删除一条边的代价为这条边的边权,现在 Rinne 想知道完成这个游戏的最小的代价,这样她就能轻松到达 rk1 了!作为回报,她会让你的排名上升一定的数量。
输入:
4 3 1
1 2 1
1 3 1
1 4 1
输出:
1
一道简单经典的树形dp的题目.
主要思路:
下面是具体的代码部分:
#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; }
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。