题目网址：https://ac.nowcoder.com/acm/problem/54148

题目描述：

Venn想要收集一些货物。Venn有一颗n个节点的树，一开始Venn在1号节点，其他每个节点都有一定的货物储备，Venn只要经过那些节点，就可以收集到节点的所有货物。每个节点的货物只能收集一次。
显然，Venn并不能轻易的收集所有的货物。每一条连接着两个节点的路径，都有一个邪恶的怪物镇守。Venn的武力值必须不小于怪物的武力值才能安全地从这条路径上通过。
Venn一开始的武力值是0，但是她可以选择健身来提升自己的武力值。每健身一分钟，就会提升一点武力值。Venn并不想收集所有的货物，只要最终收集到的货物总量不低于W就可以了。Venn一旦开始收集，就不能再健身了。但是Venn的速度很快，可以认为收集货物和从路径上经过都不需要时间。
由于Venn还急着去颓废，所以她想让你帮她计算收集到指定数量的货物最少需要几分钟。

输入描述:

一行两个正整数n,W。
接下来一行，有n-1个正整数，第i个数字a_i
表示编号为i+1节点的货物储备。
接下来n-1行，每行有三个正整数u,v,w，表示有一条路径链接编号为u,v的节点，并且路径上有一个武力值为w的怪物。

输出描述:

一行一个整数，表示最小时间花费。

示例

输入
4 7
5 5 2
1 3 2
1 2 7
1 4 5

输出
5

题解：

venn的武力值一定在[1,1e9],所以只需要对这个范围使用二分法，最坏的情况是分了log2(1e9)
次，每次需要进行的操作时，判断在当前武力值下是否可以收集到w的货物。
每次的操作思想从节点1开始，遍历与它相连的每一个结点，如果可以到达，那么将这个结点放入
队列中，如此往复循环，知道队列为空，或者收集到的货物大于等于为止。
需要注意的一点是：遍历过的结点需要进行标记，当下次通过其他结点可以到达这个结点时，自动
放弃当前结点，如果不这么做。结果也是对的，只不过会出现时间超时。

AC代码

#include"iostream"
#include"cstring"
#include"vector"
#include"queue"
using namespace std;
const int maxn =1000005;
struct node{
    int yy,vaa;
};
long long int n,w;
bool Is_no(int x); 
vector<struct node>a[maxn];
int v[maxn];
int p[maxn];
int main(){
    cin>>n>>w;
    for(int i=2;i<=n;i++) cin>>v[i];
    struct node temp;
    for(int i=1;i<n;i++){
        int x,y,va;
        cin>>x>>y>>va;
        temp.yy=y,temp.vaa=va;
        a[x].push_back(temp);//存储：所有与结点x相连的结点及其之间的武力值 
        temp.yy=x;
        a[y].push_back(temp);
    }
    int l=1,r=1000000000;//典型的二分 
    while(l<=r){
        int mid=(l+r)/2;
        if(Is_no(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<r+1;
    return 0;
} 
bool Is_no(int x){//如果武力值x满足，那么返回false,否则返回true 
    memset(p,0,sizeof(p));
    long long int s=0;
    p[1]=1;
    queue<int>q;
    q.push(1);//使用队列存储经过的结点的编号 
    while(!q.empty()){
        int m=q.front();q.pop();
        int size=a[m].size();
        for(int i=0;i<size;i++){
            if(!p[a[m][i].yy]&&a[m][i].vaa<=x){
                    s+=v[a[m][i].yy],q.push(a[m][i].yy);
                    p[a[m][i].yy]=1;//对遍历过的结点标记 
            }
        }
        if(s>=w) break;
    }
    if(s>=w) return false;
    else return true;
}

注：

本文章由白菜茄子原创，如有引用，请注明出处。

打卡第一天 2020/03/12 星期四