题目背景
冴月麟和魏潇承是好朋友。
题目描述
冴月麟为了守护幻想乡,而制造了幻想乡的倒影,将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了,但是她给前来救她的魏潇承留了一个线索。
她设置了一棵树(有根)。树的每一条边上具有割掉该边的代价。
魏潇承需要计算出割开这棵树的最小代价,这就是冴月麟和魏潇承约定的小秘密。
帮帮魏潇承吧。
注:所谓割开一棵有根树,就是删除若干条边,使得任何任何叶子节点和根节点不连通。
输入输出格式
输入格式:
输入第一行两个整数n,S表示树的节点个数和根。
接下来n-1行每行三个整数a、b、c,表示a、b之间有一条代价为c的边。
输出格式:
输出包含一行,一个整数,表示所求最小代价。
输入输出样例
输入样例#1:
4 1
1 2 1
1 3 1
1 4 1
输出样例#1:
3
输入样例#2:
4 1
1 2 3
2 3 1
3 4 2
输出样例#2:
1
说明
对于20%的数据,n <= 10
对于50%的数据,n <= 1000
对于100%的数据,n <= 100000
树形dp
令f[x]为切断x与其叶子节点的最小费用
令v=son(x)
如果切割该边的费用小于f[v],那么切这条边就行了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
int next,to,dis;
}edge[];
int num,head[],f[],n,root,ans;
void add(int u,int v,int dis)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
edge[num].dis=dis;
}
void dfs(int x,int pa)
{int i;
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (v!=pa)
{
dfs(v,x);
f[x]+=min(f[v],edge[i].dis);
}
}
if (f[x]==) f[x]=2e9;
}
int main()
{int i,a,b,c;
cin>>n>>root;
for (i=;i<=n-;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs(root,);
ans=f[root];
cout<<ans;
}