Description

传送门

Solution

看到那个式子,显然想到分数规划。。。(不然好难呢)

然后二分答案,则每条边的权值设为g(e)-ans。最后要让路径长度在[L,U]范围内的路径权值>=0

接下来我们就要找路径了。。

考虑树形dp或者分治。

假如是树形dp需要用长链剖分优化。

我的写法是点分治,非常暴力的思路em。就是枚举经过某个点的路径,注意判断长度。mx[i]记录子树内深度为i的点到目前重心的最大权值。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int inf=0x3f3f3f3f;
const double eps=1e-;
int n,L,U,x,y,v;
struct pas{int y,nxt,real_dis;}g[];int h[],tot=; bool vis[]; int sz[],dep[],mx_sz[],S,rt;
void get_rt(int x,int f)
{
sz[x]=;dep[x]=dep[f]+;mx_sz[x]=;
for (int i=h[x];i;i=g[i].nxt)
if (g[i].y!=f&&!vis[g[i].y])
{
get_rt(g[i].y,x),sz[x]+=sz[g[i].y];mx_sz[x]=max(mx_sz[x],sz[g[i].y]);
}
mx_sz[x]=max(mx_sz[x],S-sz[x]);
if (mx_sz[x]<mx_sz[rt]) rt=x;
}
double dis[],mx[];
int fa[];
int q[],dis_q[],l,r;
bool check(int x,double d)
{
int _sz=,u,v;
for (int i=h[x];i;i=g[i].nxt)
{
fa[g[i].y]=x;
l=,r=;q[]=g[i].y;dis[g[i].y]=g[i].real_dis-d;dep[g[i].y]=;
while (l<=r)
{
u=q[l];l++;
if (dep[u]>U) break;
for (int t=h[u];t;t=g[t].nxt)
if (!vis[g[t].y]&&g[t].y!=fa[u])
{
v=g[t].y;
fa[v]=u;
dis[v]=dis[u]+g[t].real_dis-d;
dep[v]=dep[u]+;
if (dep[v]>U) break;
q[++r]=v;
}
}
int re=r,now=_sz;l=,r=;
for (int j=;j<=re;j++)
{
u=q[j];
while (now>=&&dep[u]+now>=L)
{
while (l<=r&&mx[dis_q[r]]<mx[now]) r--;
dis_q[++r]=now;now--;
}
while (l<=r&&dis_q[l]+dep[u]>U) l++;
if (l<=r&&dis[u]+mx[dis_q[l]]>=) return ;
}
for (int t=_sz+;t<=dep[q[re]];t++) mx[t]=-inf;
for (int t=;t<=re;t++) mx[dep[q[t]]]=max(mx[dep[q[t]]],dis[q[t]]);
_sz=max(_sz,dep[q[re]]);
}
return ;
} double lim_l=1e9,lim_r=,ans=;
void solve(int x)
{
rt=;get_rt(x,);vis[rt]=;
double l=lim_l>ans?lim_l:ans,r=lim_r,mid;
while (r-l>eps)
{
mid=(l+r)/;
if (check(rt,mid)) l=mid;else r=mid;
}ans=l;
for (int i=h[rt];i;i=g[i].nxt)
if (!vis[g[i].y]&&sz[g[i].y]>=L)
{
S=sz[g[i].y];solve(g[i].y);
}
}
int main()
{
scanf("%d%d%d",&n,&L,&U);
for (int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&v);
g[++tot]=pas{y,h[x],v};h[x]=tot;
g[++tot]=pas{x,h[y],v};h[y]=tot;
lim_l=min(lim_l,(double)v);
lim_r=max(lim_r,(double)v);
}
mx_sz[]=inf;dep[]=-;
S=n;solve();
printf("%.3f",ans);
}

最新文章

  1. linux中vi编辑器的使用
  2. 【PowerOJ1739】 魔术球问题
  3. 免费的ER 设计软件调研
  4. PAT天梯赛练习题 L3-010. 是否完全二叉搜索树(完全二叉树的判断)
  5. 当数据库某张表数据发生变化时,更新c#程序中缓存的用法
  6. Regist
  7. Log4j2在WEB项目中配置
  8. l2tp vpn客户端
  9. LeetCode: Word Break I &amp;&amp; II
  10. CentOS(七)--Linux文件类型及目录配置
  11. python之6-3嵌套函数
  12. MyEclipse第一个Servlet程序 --解决Win7系统下MyEclipse与Tomcat连接问题
  13. Query语句对系统性能的影响
  14. 谈谈字符集编码及gb2312、utf-8编码原理
  15. setTimeout,setInterval运行原理
  16. Linux集群问题~浅谈
  17. 【Mybatis】使用Mybatis-Generator自动生成entity、dao、mapping
  18. bak
  19. ArrayList 实现随机点名
  20. Fenng早年间对推荐系统的思考

热门文章

  1. POI读取单元格信息及单元格公式
  2. CF Gym 100637B Lunch(拆分子问题)
  3. Codeforces Round #441 (Div. 2)【A、B、C、D】
  4. Guava包学习--Multiset
  5. webpack中使用babel处理es6语法
  6. Js 中的 this
  7. SpringBoot实战(三)之使用RestFul Web服务
  8. 日期字符串解析--SimpleDateFormat严格限制日期转换setLenient(false)
  9. oracle 查看表空间以及剩余量
  10. +QFTPOPEN: 603,0 怎么把这样一个字符串中的 603 提取出来给一个 uint32_t 的变量那