网站制作报价维持地建网络,福建金融公司网站建设,iis下建立asp网站,江西百度推广开户多少钱吉吉王国
题意#xff1a;
n个点#xff0c;m个边#xff0c;有边权#xff0c;现在要求叶子节点无法与1号点连通#xff0c;要求切断的总长度不能超过m#xff0c;且切断的最长的长度尽可能断
题解#xff1a;
题意的前半部分可以确定是树形dp#xff0c;后半部分…吉吉王国
题意
n个点m个边有边权现在要求叶子节点无法与1号点连通要求切断的总长度不能超过m且切断的最长的长度尽可能断
题解
题意的前半部分可以确定是树形dp后半部分可以确定为是二分 树形dp部分和这个题差不多 Rinne Loves Edges 我们二分一个长度的上限然后在dp中限制判断二分的值是否合理
代码
#include bits/stdc.h
#define endl \nusing namespace std;const int maxn1e310;
typedef long long ll;
vectorpairll,ll edge[maxn];
ll sz[maxn];ll n,m;
void dfs(ll x,ll fa,ll mid){ //mid为每条道路限制长度bool flagfalse;for(auto i:edge[x]){if(i.firstfa) continue;dfs(i.first,x,mid);flagtrue;if(i.secondmid) sz[x]sz[i.first];else sz[x]min(i.second,sz[i.first]);}if(!flag) sz[x]1e9;
}bool che(ll x){ //最长的道路memset(sz,0,sizeof sz);dfs(1,0,x);//coutsz[1]endl;if(sz[1]m) return true;else return false;
}int main(){cinnm;for(ll i0;in-1;i){ll x,y,z;cinxyz;edge[x].push_back({y,z});edge[y].push_back({x,z});}ll l1,rm1;while(lr){ll mid(lr)/2;if(che(mid))rmid;else lmid1;}if(lm1) cout-1endl;else coutlendl;}
