题面：P5021 赛道修建
题解：二分答案，用Dfs进行判断，multiset维护。
Dfs(x,fa,Lim)用来计算以x为根的子树中有多少符合条件的路径，并返回剩余未使用的最长路径长。
贪心思想很显然是正确的。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<set> 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 #define min(a,b) ((a)<(b)?(a):(b)) 6 using namespace std; 7 inline int rd(){ 8 int x=0,f=1; char c=getchar(); 9 while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} 10 while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} 11 return f*x; 12 } 13 const int maxn=5e4+5,inf=(1<<30)-5; 14 int N,M,num_edge=0,edge_head[maxn],u,v,w,l=inf,r=0,mid; 15 int cnt,t,a,mx; 16 multiset<int>num[maxn]; 17 multiset<int>::iterator it; 18 struct Edge{ int to,nx,dis; }edge[maxn<<1]; 19 inline void Add_edge(int from,int to,int dis){ 20 edge[++num_edge].nx=edge_head[from]; 21 edge[num_edge].to=to; 22 edge[num_edge].dis=dis; 23 edge_head[from]=num_edge; 24 } 25 int Dfs(int x,int fa,int Lim){ 26 num[x].clear(); 27 for(int i=edge_head[x];i;i=edge[i].nx){ 28 int y=edge[i].to; 29 if(y==fa) continue; 30 t=edge[i].dis+Dfs(y,x,Lim); 31 if(t>=Lim) cnt++; 32 else num[x].insert(t); 33 } 34 mx=0; 35 while(!num[x].empty()){ 36 it=num[x].begin(); 37 a=*it; num[x].erase(it); 38 it=num[x].lower_bound(Lim-a); 39 if(it!=num[x].end()){ 40 cnt++; 41 num[x].erase(it); 42 } 43 else mx=a; 44 } 45 return mx; 46 } 47 inline bool Check(int mid){ 48 cnt=0; 49 Dfs(1,0,mid); 50 if(cnt>=M) return 1; 51 return 0; 52 } 53 int main(){ 54 N=rd(); M=rd(); 55 for(int i=1;i<N;i++){ 56 u=rd(); v=rd(); w=rd(); 57 Add_edge(u,v,w); 58 Add_edge(v,u,w); 59 l=min(l,w); r+=w; 60 } 61 r=r/M; 62 while(l<=r){ 63 mid=(l+r)>>1; 64 if(Check(mid)) l=mid+1; 65 else r=mid-1; 66 } 67 printf("%d\n",r); 68 return 0; 69 }
By:AlenaNuna