Rinne Loves Edges

題意：

有n給點，m個邊，每個邊有邊權，給你一個點S，問最少花多少代價，可以讓葉子節點無法與S點連通

題解：

dp[u]:表示u到葉子節點的最短費用的和
dp[u]+=min(dp[v],w);

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2e5+9; vector<pair<ll,ll> >vec[maxn]; ll dp[maxn]; ll n,m,s; ll d[maxn]; void dfs(ll u,ll fa){if(d[u]==1&&u!=s)return ;dp[u]=0;for(int i=0;i<vec[u].size();i++){ll v=vec[u][i].first;ll w=vec[u][i].second;if(v==fa)continue;dfs(v,u);dp[u]+=min(dp[v],w);}} int main() {cin>>n>>m>>s;for(int i=1;i<=m;i++){ll u,v,w;cin>>u>>v>>w;vec[u].push_back(make_pair(v,w));vec[v].push_back(make_pair(u,w));d[u]++;d[v]++;} memset(dp,0x3f3f3f,sizeof(dp));dfs(s,0);cout<<dp[s];return 0; }

總結

以上是生活随笔為你收集整理的Rinne Loves Edges的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。