Solution

由题意可知给定的图是一棵树。树上的最优化问题可以想到树形 。

按照常用的状态设计方式，可以设 为根节点为 的最少代价。使以 为根的子树的叶子节点无法到达 的方式有两种：

• 割断与 直接相连的边
• 割断与 的子节点直接相连的边

两种方式取最小值即可。故状态转移方程为

其中 为与 直接相连的子节点。

因此可以以 节点为根，进行 ，目标状态为 。

时间复杂度： 。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const ll maxn=2e5+10;
ll n,m,s,cnt,d[maxn],hd[maxn],f[maxn];
struct edge{
    ll t,v,w;
}e[maxn<<1];
void add(ll x,ll y,ll z){
    cnt++;
    e[cnt].t=hd[x];
    e[cnt].v=y;
    e[cnt].w=z;
    hd[x]=cnt;
}
void Dfs(ll u,ll fa){
    if(d[u]==1&&u!=s)
        return;
    f[u]=0;
    for(int i=hd[u];i!=0;i=e[i].t)
        if(e[i].v!=fa){
            Dfs(e[i].v,u);
            f[u]+=min(f[e[i].v],e[i].w);
        }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    ll x,y,z;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
        d[x]++,d[y]++;
    }
    memset(f,0x7f,sizeof(f));
    Dfs(s,0);
    cout<<f[s];
    return 0;
}