牛客网

  1. 题目：

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

题目描述 Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。 她现在拿到了一个 n 个节点 m
条边的无向连通图，每条边有一个边权 wi 现在她想玩一个游戏：选取一个 “重要点” 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 范围内

  1. 题解：

仔细观察题中给的数据m=n-1，其实就是给你一个树，而被删除度为1的点就是这个树的叶子节点，给你的s就是这个树的根
那一切就很清楚了：给你一个树和根节点，让你通过删边使得根节点与叶子节点不相连，问你怎么删值最小
这个是树形dp问题，我们要做的就是在搜索树的过程中不断处理数据
凡是dp问题，都有状态转移，就是一个大问题可以小问题
s为根节点时，要删去一些边让s与每个叶子节点不连通，其实就是让x为根节点的子树删去一些边，使得s和x的子树上每个叶子节点不连通。
两种情况：一个就是删去x与他儿子y的边
另一个就是看以y为子树的根节点的最小情况。
我们取较小值
f[x]+=min(f[y],edge[i].w);
edge[i].w是指当前节点x与其子节点y的距离
具体看代码吧

  1. 代码： 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+3;
int f[maxn];
struct node{
    int u,v,w,next;
}edge[maxn*2];
int root[maxn];
int head[maxn];
int cnt=0;
    int n,m,s;
void addt(int u,int v,int w)
{
    edge[++cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int x,int fa)
{
    if(x!=s&&root[x]==1)f[x]=-1;//如果这个是叶子节点，就断绝与父亲的关系 
    //根节点s也有可能度为1，所以要除s之外
    int now;//当前点x的子节点
    //关系(fa-->x-->now)
    for(int i=head[x];i;i=edge[i].next)
    {
        now=edge[i].v;

        if(now==fa)continue;//因为是无向图，我们要防止返回到父亲节点

        dfs(now,x);//继续向下
        if(f[now]==-1)f[x]+=edge[i].w;//这个我们已经给断绝关系了，只加当前边的权值
        else 
        f[x]+=min(f[now],edge[i].w);//考虑两个方面
    }
}
int main()
{

    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        addt(u,v,w);
        addt(v,u,w);//链式前向星
        root[u]++;
        root[v]++;
     } 
     dfs(s,0);
     printf("%d",f[s]);
     return 0;
}