【NOIP2018】赛道修建【二分答案】【贪心】

传送门

现在来看去年的题要简单多了。

这道题题面明确告诉你要二分答案。

其次因为每条边只能用一次，所以我们可以确定超过mid的链直接使用，答案+1。

没到的链可以合并。而合并的时候肯定消费越少越好。这个操作可以用multiset来完成。

借此复习了一下STL的一些函数和指针的用法。

注意set的end是最后一个往外一位。multiset有count函数算多少个。

闲的没事儿可以写一个树的直径来减少二分次数。在查询的时候有点小细节注意一下。

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar(); 
	}return cnt*f;
}
int first[50003],nxt[100003],to[100003],w[100003],tot,n,m;
void add(int a,int b,int c){
	nxt[++tot]=first[a];first[a]=tot;to[tot]=b;w[tot]=c;
}
multiset<int> q[50003];
multiset<int>::iterator it;int maxx;
int dfs1(int u,int fa){
	int sum1,sum2=0;
	for(int i=first[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		sum2=max(sum2,dfs1(v,u)+w[i]);
		if(sum2>sum1)swap(sum2,sum1);
	}maxx=max(maxx,sum1+sum2);return sum1;
}int ans=0;
int dfs(int u,int fa,int key){
	q[u].clear();int val;
	for(int i=first[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		val=dfs(v,u,key)+w[i];
		if(val>=key)ans++;
		else q[u].insert(val);
	}int Max=0;
	while(!q[u].empty()){
		if(q[u].size()==1){
			Max=max(Max,*q[u].begin());
			return Max;
		}
		it=q[u].lower_bound(key-*q[u].begin());
		if(it==q[u].begin()&&q[u].count(*it))it++;
		if(it==q[u].end()){
			Max=max(Max,*q[u].begin());q[u].erase(q[u].find(*q[u].begin()));
		}else{
			ans++;q[u].erase(q[u].find(*it));
			q[u].erase(q[u].find(*q[u].begin()));
		}
	}return Max;
}
bool check(int x){
	ans=0;
	dfs(1,0,x);if(ans>=m)return 1;return 0;
}
int main(){
	n=in;m=in;
	for(int i=1;i<n;i++){
		int a=in;int b=in;int c=in;add(a,b,c);add(b,a,c);
	}
	dfs1(1,0);
	int l=1,r=maxx;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid))l=mid;else r=mid-1;
	}cout<<l;
	return 0;
}