弱鸡萌新2018年难忘的骗分之旅
花了2个小时骗分2333
题意
从n个点构成的的树中取出m条边不重复路径，使得最小的路径最长
思路
-
由于没有一个确定的限制且问题具有单调性，首先肯定想到二分答案，设该数为x，那么需要找出长度大于等于x的路径条数
-
对于一个子树i，考虑它的贡献，分为两种：① i子树中选一条或两条链，使它们拼起来大于等于x ，② 父亲节点通过连向i子树的这条边使用i子树中的一条链，这个贡献最多只能有一次（因为父亲到i的边只有一条）。那么把哪一条链贡献给父亲呢？使用贪心策略
-
贪心：让i子树自己内部能配对的尽量配对，达到最多的配对数之后，将未配对的最大链贡献给父亲即可。这样的正确性是显然的，因为如果i子树中有两条链本来可以配对却不让它们配对，那么路径数少1，把其中一条贡献给父亲，通过2中叙述可知，这样最多使路径数加1，但是会多浪费一些父亲子树中的一些边，肯定不如直接配对。
-
在使配对数最多的情况下，由于还要把未配对最大链贡献给父亲，所以这时候可以二分最大的链，检验如果没有用这条链，是否还能达到最大匹配数，如果能则说明可以不用这条链，即可以贡献给父亲
实现
上述思路总结起来的实现就是： 二分+排序+二分
排序用vector或者multiset即可
Code：
#include<bits/stdc++.h>
#define N 50005
using namespace std;
const int INF = 2000000000;
int n,m,limit,sum;
vector <int> e[N];
struct Edge
{
int next,to,dis;
}edge[N<<1];int head[N],cnt=1;
void add_edge(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
bool ck(int rt,int pos,int l,int r,int goal)//不用pos是否能凑出goal个
{
int tot=0;
while(l<r)
{
if(r==pos) --r;
if(l==pos) ++l;
while((e[rt][l]+e[rt][r]<limit||l==pos)&&(l<r)) ++l;
if(!(l<r)) break;
++tot;++l;--r;
}
return (tot>=goal);
}
int dfs(int rt,int fa)
{
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
e[rt].push_back(edge[i].dis+dfs(v,rt));
}
if(e[rt].empty()) return 0;
sort(e[rt].begin(),e[rt].end());
int l=0,r=(int)e[rt].size()-1;
while(e[rt][r]>=limit) ++sum,--r;//单独成链
int rest=r+1,tot=0;
while(l<r)
{
while(e[rt][l]+e[rt][r]<limit&&(l<r)) ++l;
if(!(l<r)) break;
++tot;++l;--r;
}
sum+=tot;
if(tot*2==rest) return 0;//完全配对
//否则一定剩下至少一个
l=0;r=rest-1;int ret=0;
while(l<=r)//二分出返回值
{
int mid=(l+r)>>1;
if(ck(rt,mid,0,rest-1,tot)) l=mid+1,ret=max(mid,ret);
else r=mid-1;
}
return e[rt][ret];
}
bool check(int x)//求所有大于等于x长度的赛道
{
for(int i=1;i<=n;++i) e[i].clear();
limit=x;sum=0;
dfs(1,0);
return (sum>=m);
}
int main()
{
read(n);read(m);
for(int i=1;i<n;++i)
{
int x,y,z;
read(x);read(y);read(z);
add_edge(x,y,z);
add_edge(y,x,z);
}
int l=0,r=INF,ans=-INF;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) l=mid+1,ans=max(ans,mid);
else r=mid-1;
}
printf("%d
",ans);
return 0;
}