本文共 1170 字，大约阅读时间需要 3 分钟。

题意

给出n个点，n-1对关系，表示两点之间是否连通，1为连通，2为断。选中一个点，可以修复1到该点的路径上所有坏的边。求最少要选出哪些点。

思路

由于顶点数比较多，然后带权值，我们采用链式前向星建边，然后dfs。

在回溯的过程中，如果在当前点的儿子存在有问题的边，那就不选这个点

反之，如果没有并且连接这个点的边是有问题的边，这个点就是所求的点。

回溯时情况：

• 儿子存在有问题的边 不选择这个点 return 1
• 当前状态为2并且儿子下没有有问题的边，保存这个点 return 1
• 其他情况 return 0

code

#include
   
    #define endl '\n'using namespace std;const int maxn=2e5+5;int n,cnt,k;int head[maxn],vis[maxn];int ans[maxn],num[maxn];struct node{
       int to,nex,w;}e[maxn<<1];void init(){
       memset(head,-1,sizeof(head));    cnt=0,k=0;    memset(vis,0,sizeof(vis));}void add(int u,int v,int w){
       e[cnt].to=v;    e[cnt].nex=head[u];    e[cnt].w=w;    head[u]=cnt++;}int dfs(int u,int op){
       vis[u]=1;    for(int i=head[u];~i;i=e[i].nex){
           int v=e[i].to,w=e[i].w;        if(!vis[v])            num[u]+=dfs(v,w);    }    if(num[u])        return 1;    if(op==2&&num[u]==0){
           ans[k++]=u;        return 1;    }    return 0;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>n;    init();    for(int i=1;i<=n-1;i++){
           int u,v,w;        cin>>u>>v>>w;        add(u,v,w);        add(v,u,w);    }    dfs(1,-1);    cout<
    
     <
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/104142608 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！