Rinne Loves Edges
Rinne Loves Edges
https://ac.nowcoder.com/acm/problem/22598
题意
有一颗树，可以删去一些边，代价是边权。
现在要使得叶子节点和根节点不连通，求删边的最小代价。
分析
M=N−1，这也太坑了吧。
举个栗子
我们可以选择删去这条边，或者删去
和
这条边，显然选代价小的。
我们可以通过求出所需的代价。
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 101110;
const int M = 1e9+7;
int n,m,s,ans;
vector<pii> v[maxn];
int dfs(int u,int pre,int res) //res表示u和pre边的代价
{
int tmp = 0; //tmp表示删除全部子树的最小代价
for(auto i : v[u])
{
if(i.first == pre) continue;
tmp += dfs(i.first,u,i.second);
}
if(tmp == 0) tmp = res;
//if(u == 1) cout<<tmp<<' '<<res<<endl;
return min(tmp,res);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s;
for(int i = 1,x,y,z; i <= m; i++)
{
cin>>x>>y>>z;
v[x].push_back({y,z});
v[y].push_back({x,z});
}
cout<<dfs(s,0,1e18)<<endl;
return 0;
} 
查看17道真题和解析