洛谷 P4292 [WC2010]重建计划 解题报告

P4292 [WC2010]重建计划

题目描述

\(X\)国遭受了地震的重创, 导致全国的交通近乎瘫痪,重建家园的计划迫在眉睫。\(X\)国由\(N\)个城市组成, 重建小组提出,仅需建立\(N-1\)条道路即可使得任意两个城市互相可达。于是,重建小组很快提出了一个包含\(N-1\)条道路的方案,并满足城市之间两两可达,他们还计算评估了每条道路\(e\)建设之后可以带来的价值\(v(e)\)。

由于重建计划复杂而艰难,经费也有一定限制。因此,*要求第一期重建工程修建的道路数目为\(k\)条,但需满足\(L ≤ k ≤ U\), 即不应少于\(L\)条,但不超过\(U\)条。同时,为了最大化利用率,要求建设的这些道路恰好组成一条简单路径,即所建设的\(k\)条路径可以构成一个排列\(e_1 = (p_1, q_1), e_2 = (p_2, q_2),\dots, e_k = (p_k, q_k)\), 对于 \(1 ≤ i < k\), 有\((q_i = p_i+1)\)。

重建小组打算修改他们的原有方案以满足要求,即在原有的N-1条道路中寻找一条路径S作为新的方案,使得新方案中的道路平均价值

\[AvgValue = \frac{\sum _{e \in S} v(e)}{|S|}
\]

最大。这里\(v(e)\)表示道路\(e\)的价值,\(|S|\)表示新方案中道路的条数。请你帮助重建小组寻找一个最优方案。 注: 在本题中\(L\)和\(U\)的设置将保证有解。

输入输出格式

输入格式:

第一行包含一个正整数\(N\),表示\(X\)国的城市个数。

第二行包含两个正整数\(L\)、\(U\),表示*要求的第一期重建方案中修建道路数的上下限。

接下来的\(N-1\)行描述重建小组的原有方案,每行三个正整数\(a_i, b_i, v_i\),分别表示道路\((a_i, b_i)\),其价值为\(v_i\)。其中城市由\(1\dots N\)标号。

输出格式:

仅包含一行,为一个实数\(AvgValue\),即最大平均价值。

小数点后保留三位。

说明

对于\(20\%\)的数据,\(N ≤ 5 000\);

另有\(30\%\)的数据,\(N ≤ 100 000\), 原有方案恰好为一条路径(链);

对于\(100\%\)的数据,\(N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, v_i ≤ 10^6\)。


鉴于本辣鸡代码写的天昏地暗,把自己恶心的不行,所以思路也懒得好好说了,简单说一下吧。

分数规划+线段树维护长链剖分

二分之后需要找一条长度为\([l,r]\)之间的链的边权和大于\(0\)

显然可以\(O(n^2)\)进行\(dp\),然后使用长链剖分继承重儿子。

发现继承重儿子的过程需要开一个线段树维护。

只开一个线段树维护\(dfs\)序,然后就可以很方便的进行偏移,加连接重儿子的边时可以直接区间打\(tag\)


Code:

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
const int N=1e5+10;
int head[N],to[N<<1],Next[N<<1],cnt;
double edge[N<<1];
void add(int u,int v,double w)
{
to[++cnt]=v,Next[cnt]=head[u],edge[cnt]=w,head[u]=cnt;
}
double tag[N<<2],mx[N<<2];
int n,lp,rp;
using std::min;
using std::max;
#define ls id<<1
#define rs id<<1|1
void pushdown(int id)
{
if(tag[id]<-1e17) return;
if(mx[ls]<-1e17) mx[ls]=tag[id];
else mx[ls]+=tag[id];
if(mx[rs]<-1e17) mx[rs]=tag[id];
else mx[rs]+=tag[id];
if(tag[ls]<-1e17) tag[ls]=tag[id];
else tag[ls]+=tag[id];
if(tag[rs]<-1e17) tag[rs]=tag[id];
else tag[rs]+=tag[id];
tag[id]=-1e18;
}
double query(int id,int L,int R,int l,int r)
{
if(L==l&&R==r) return mx[id];
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) return query(ls,L,Mid,l,r);
else if(l>Mid) return query(rs,Mid+1,R,l,r);
else return max(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));
}
void change(int id,int L,int R,int l,int r,double d)
{
if(L==l&&R==r)
{
if(mx[id]<-1e17) mx[id]=d;
else mx[id]+=d;
if(tag[id]<-1e17) tag[id]=d;
else tag[id]+=d;
return;
}
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) change(ls,L,Mid,l,r,d);
else if(l>Mid) change(rs,Mid+1,R,l,r,d);
else change(ls,L,Mid,l,Mid,d),change(rs,Mid+1,R,Mid+1,r,d);
mx[id]=max(mx[ls],mx[rs]);
}
void modify(int id,int l,int r,int p,double d)
{
if(l==r) {mx[id]=max(mx[id],d);return;}
pushdown(id);
int mid=l+r>>1;
if(p<=mid) modify(ls,l,mid,p,d);
else modify(rs,mid+1,r,p,d);
mx[id]=max(mx[ls],mx[rs]);
}
int dis[N],ws[N],dfn[N],dfsclock;
double ans;
void dfsinit(int now,int fa)
{
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa)
{
dfsinit(v,now);
if(dis[to[ws[now]]]<dis[v]) ws[now]=i;
}
dis[now]=dis[to[ws[now]]]+1;
}
int tn,ty;
void dfsseg(int id,int L,int R,int l,int r,int p)
{
if(L==R)
{
int len=l+1-tn;
if(ty) modify(1,1,n,len+dfn[p],mx[id]);
else if(len+dis[p]-1>=lp&&len<rp)
ans=max(ans,mx[id]+query(1,1,n,max(dfn[p]+1,dfn[p]+lp-len),min(dfn[p]+rp-len,dfn[p]+dis[p]-1)));
return;
}
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) dfsseg(ls,L,Mid,l,r,p);
else if(l>Mid) dfsseg(rs,Mid+1,R,l,r,p);
else dfsseg(ls,L,Mid,l,Mid,p),dfsseg(rs,Mid+1,R,Mid+1,r,p);
}
void dfs(int now,int fa)
{
dfn[now]=++dfsclock;
if(ws[now])
{
dfs(to[ws[now]],now);
change(1,1,n,dfn[now]+1,dfn[now]+1,edge[ws[now]]);
if(dis[now]>2)
change(1,1,n,dfn[now]+2,dfn[now]+dis[now]-1,edge[ws[now]]);
}
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa&&i!=ws[now])
{
dfs(v,now);tn=dfn[v];
change(1,1,n,dfn[v],dfn[v]+dis[v]-1,edge[i]);
ty=0,dfsseg(1,1,n,dfn[v],dfn[v]+dis[v]-1,now);
ty=1,dfsseg(1,1,n,dfn[v],dfn[v]+dis[v]-1,now);
}
if(dis[now]-1>=lp)
ans=max(ans,query(1,1,n,dfn[now]+lp,min(dfn[now]+rp,dfn[now]+dis[now]-1)));
}
bool check(double d)
{
for(int i=1;i<=cnt;i++) edge[i]-=d;
for(int i=1;i<=n<<2;i++) mx[i]=tag[i]=-1e18;
dfsclock=0,ans=-1e18;dfs(1,0);
for(int i=1;i<=cnt;i++) edge[i]+=d;
return ans>=0;
}
int main()
{
scanf("%d%d%d",&n,&lp,&rp);
double l=1e18,r=-1e18,w;
for(int u,v,i=1;i<n;i++)
{
scanf("%d%d%lf",&u,&v,&w),add(u,v,w),add(v,u,w);
l=min(l,w),r=max(r,w);
}
dfsinit(1,0);
while(l+1e-4<r)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.3lf\n",l);
return 0;
}

2018.12.14

上一篇:hadoop之hdfs命令详解


下一篇:position总结图