DZY Loves Planting
逆天题。
想到二分,判断用网络流,但是好像 n 有点大。
我们想尽量让每个点的 g 能大于下界,所以我们尽量往大的边走,其实就是尽量不走小的边。
所以考虑将边从小到大排序,每次合并两端的连通块,如果剩下点的 x 总和小于总点数就只能内部消化。
又因为这已经是最劣的情况(之前的点分配出去能走到大于当前边权的点)所以直接输出即可。
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=3005;
int n,fa[MAXN],siz[MAXN],sx[MAXN],S;
void read(int &x){
x=0;
int f=1;char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;
s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);
s=getchar();
}
x*=f;
}
struct ren{
int x,y,w;
bool operator<(const ren &a)const{return w<a.w;}
}a[MAXN];
bool pd;
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
fa[i]=i;siz[i]=1;
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
}
fa[n]=n;
for(int i=1;i<=n;i++) scanf("%d",&sx[i]),S+=sx[i];
sort(a+1,a+n);
for(int i=1;i<n;i++){
int fx=Find(a[i].x),fy=Find(a[i].y);
if(fx==fy) continue;
siz[fy]+=siz[fx];sx[fy]+=sx[fx];fa[fx]=fy;
if(siz[fy]>S-sx[fy]){
printf("%d",a[i].w);pd=1;break;
}
}
if(!pd) printf("%d",a[n-1].w);
return 0;
}