题意：
在一棵树上选出m条路径，这些路径不能共用任意一条边
问这些路径中最小的一条路最大是多少
这道题的部分分十分有意思，搞了一搞
第一种情况是m=1，即只选出一条最长的路径
显然是计算树的直径
int fa[N],ans=0;
int dfs1(int u)
{
int sum1=0,sum2=0;
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa[u]) continue;
fa[v]=u;
sum2=max(sum2,dfs1(v)+edge[i].dis);
if(sum2>sum1) swap(sum2,sum1);
}
ans=max(ans,sum1+sum2);
return sum1;
}
ans即为所求
第二种情况是地图没有分支，为一条链
那就是说在序列上面二分，很经典的题了
bool check(int x)
{
int d=0,now=0;
for(register int i=1;i<n;++i)
{
if(now+a[i]>=x)
{
now=0;
d++;
}
else now+=a[i];
}
return d>=m;
}
第三种情况是菊花图，所有的u=1
直接每次枚举最长加最短，次长加次短，……，统计最小值即可
if(juhua)//菊花图直接判断即可
{
for(register int i=head[1];i;i=edge[i].next)
{
int vv=edge[i].to;
a[vv-1]=edge[i].dis;
}
sort(a+1,a+n,cmp);
int ans=0x3f3f3f3f;
for(register int i=1;i<=m;++i)
ans=min(ans,a[i]+a[2*m-i+1]);
printf("%d
",ans);
return 0;
}
所以总的代码是这样
#include<bits/stdc++.h>
#define N 50005
#define mid ((l+r+1)>>1)
using namespace std;
int n,m,u,v,w;
struct Edge
{
int next,to,dis;
}edge[N<<1];
int cnt=0,head[N];
inline 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>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
int fa[N],ans=0;
int dfs1(int u)
{
int sum1=0,sum2=0;
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa[u]) continue;
fa[v]=u;
sum2=max(sum2,dfs1(v)+edge[i].dis);
if(sum2>sum1) swap(sum2,sum1);
}
ans=max(ans,sum1+sum2);
return sum1;
}
int a[N];
void dfs2(int u)
{
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa[u]) continue;
fa[v]=u;
dfs2(v);
a[u]=edge[i].dis;
}
}
bool check(int x)
{
int d=0,now=0;
for(register int i=1;i<n;++i)
{
if(now+a[i]>=x)
{
now=0;
d++;
}
else now+=a[i];
}
return d>=m;
}
bool cmp(int a,int b) {return a>b;}
int main()
{
// freopen("testdata.in","r",stdin);
read(n);read(m);
bool juhua=1,lian=1;
int sum=0;
for(register int i=1;i<=n-1;++i)
{
read(u);read(v);read(w);
sum+=w;
if(u!=1) juhua=0;
if(v!=u+1) lian=0;
add_edge(u,v,w);
add_edge(v,u,w);
}
if(m==1)//只有一条路，算直径
{
dfs1(1);
printf("%d
",ans);
return 0;
}
if(lian)//地图是一条链，相当于序列二分答案
{
dfs2(1);
int l=1,r=sum;
while(l<=r)
{
// cout<<l<<" "<<r<<" "<<mid<<endl;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d
",l);
return 0;
}
if(juhua)//菊花图直接判断即可
{
for(register int i=head[1];i;i=edge[i].next)
{
int vv=edge[i].to;
a[vv-1]=edge[i].dis;
}
sort(a+1,a+n,cmp);
int ans=0x3f3f3f3f;
for(register int i=1;i<=m;++i)
ans=min(ans,a[i]+a[2*m-i+1]);
printf("%d
",ans);
return 0;
}
return 0;
}
这么写的话就已经有55分了，性价比极高……
所以D1你就有了100+100+55=255的高分
剩下的时间可以拿来思考正解
正解其实也十分简单，等会儿写……
update：正解已迁移至这里：点我