根能抵达的节点(二分法、DFS)C++

发布时间:2024年01月12日

给定一棵由 N个节点构成的带边权树。节点编号从 0到 N?1,其中 0 号点为根节点。最初,从根节点可以抵达所有节点(包括自己)。如果我们将所有边权小于 X 的边全部删掉,那么从根节点可以抵达的节点数目就可能发生改变。
现在,给定一个整数 Y,请你找到最小的非负整数 X,使得所有边权小于 X
的边都被删掉以后,根节点能够抵达的节点数目(包括自己)不超过 Y

输入格式
第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含两个整数 N,Y。
接下来 N?1行,每行包含三个整数 U,V,W,表示点 U 和点 V 之间存在一条权值为 W 的边。

输出格式
每组数据输出一行,一个 X。
注意,X 应不小于 0。

数据范围
1≤T≤100,
1≤N≤20000,
1≤Y≤N,
0≤U,V<N,
0≤W≤107,

保证在一个测试点中,所有 N 的和不超过 105。

输入样例:
2
3 2
0 1 2
0 2 3

6 3
0 1 8
0 2 3
1 3 2
1 4 5
2 5 6

输出样例:
3
4

#include<iostream>
#include<cstring>
using namespace std;
const int N=20010,M=N*2;
int h[N],e[M],ne[M],w[M],idx; //头结点、邻接表结点、指针、权、插入的第几个结点。
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int mid,int fa) //从第u个节点遍历,mid为答案,fa为父节点
{
    int res=1; //从父节点开始可以遍历到的节点
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa||w[i]<mid) continue;//如果次节点边权小于答案,说明该节点被删除后无法到达根节点。
        res+=dfs(j,mid,u);
    }
    return res;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,y;
        cin>>n>>y;
        idx=0; //每次输出将邻接表清空
        memset(h,-1,sizeof(h));
        for(int i=0;i<n-1;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);  //树为特殊的无向图
            add(b,a,c);
        }
        int l=0,r=1e8;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(dfs(0,mid,-1)<=y) r=mid; //当答案小于y时说明答案在y左边,r=mid;
            else l=mid+1;
        }
        cout<<r<<endl;
    }
    return 0;
}
文章来源:https://blog.csdn.net/qq_46380990/article/details/135549216
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。