WC2010重建计划 - 二分法 - 点分治 - 单调队列 -
WC2010重建计划
Description
第一行包含一个正整数N，表示X国的城市个数. 第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限 接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号
输出最大平均估值，保留三位小数
Sample Input
Sample Output
20%的数据,N&=5000
30%的数据,N&=100000,原有方案恰好为一条路径
100%的数据,N&=&=L&=U&=N-1,Vi&=1000000
对于每个重心，二分一个***mid
将图中所有边减mid，问题转换为判断是否存在长为x的路径，路径边权和&=0，L&=x&=U
从重心剖开树以后，得到若干棵子树
顺序处理每棵子树，并维护mx[i]表示起点从重心出发，终点在子树内，长度为i的路径边权和最值
对于一棵子树，bfs得其所有路径长度及边权和（起点从重心出发，终点在该子树内）
由于是bfs，所以路径长度是从小到大
mx倒序是从大到小
枚举路径i，维护mx的单调递减队列(dis)
若当前mx+deep[i]&=L则mx加入队尾（维护单调）
若deep[i]+q[l]&U，则l++
#include&iostream&
#include&cstdio&
#include&cstring&
#include&cstdlib&
#include&map&
#include&ctime&
#include&vector&
#include&set&
#include&cmath&
#include&algorithm&
#define inf
#define ll long long
int read()
int x=0,f=1;char ch=getchar();
while(ch&'0'||ch&'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch&='0'&&ch&='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
int n,cnt,S,L,U,root,
struct edge{int to,next,v;}e[200005];int last[200005];
int size[100005],fa[100005],f[100005],deep[100005];
int q[100005],dq[100005];
bool mark[100005];
double dis[100005],mx[100005];
void insert(int u,int v,int w)
e[++cnt].to=v;e[cnt].next=last[u];last[u]=e[cnt].v=w;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=e[cnt].v=w;
void getroot(int x,int fa)
size[x]=1;f[x]=0;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa&&!mark[e[i].to])
getroot(e[i].to,x);
size[x]+=size[e[i].to];
f[x]=max(f[x],size[e[i].to]);
f[x]=max(f[x],S-size[x]);
if(f[x]&=f[root])root=x;
bool jud(int rt,double M)
for(int t=last[rt];t;t=e[t].next)
if(mark[e[t].to])
int head=0,tail=1;
q[0]=e[t].
fa[e[t].to]=deep[e[t].to]=1;
dis[e[t].to]=(double)e[t].v-M;
while(head!=tail)
int now=q[head];head++;
for(int i=last[now];i;i=e[i].next)
if(e[i].to!=fa[now]&&!mark[e[i].to])
q[tail]=e[i].
fa[e[i].to]=deep[e[i].to]=deep[now]+1;
dis[e[i].to]=dis[now]+e[i].v-M;
int l=1,r=0,now=
for(int i=0;i&i++)
int x=q[i];
while(deep[x]+now&=L&&now&=0)
while(l&=r&&mx[dq[r]]&mx[now])r--;
while(l&=r&&deep[x]+dq[l]&U)l++;
if(l&=r&&dis[x]+mx[dq[l]]&=0)return 1;
for(int i=up+1;i&=deep[q[tail-1]];i++)mx[i]=-
for(int i=0;i&i++)
int x=q[i];
mx[deep[x]]=max(mx[deep[x]],dis[x]);
up=max(up,deep[q[tail-1]]);
void cal(int x)
double l=ans,r=lim,
while(r-l&0.0001)
mid=(l+r)/2;
if(jud(x,mid))l=
void solve(int x)
mark[x]=1;
for(int i=last[x];i;i=e[i].next)
if(!mark[e[i].to])
root=0;S=size[e[i].to];
getroot(e[i].to,0);
if(size[e[i].to]&L)
solve(root);
int main()
freopen("rebuild.in","r",stdin);
freopen("rebuild.out","w",stdout);
n=read();L=read();U=read();
for(int i=1;i&n;i++)
int u=read(),v=read(),w=read();
insert(u,v,w);
lim=max(lim,w);
root=0;S=n;
getroot(1,0);
solve(root);
printf("%.3lf",ans);
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132
#include&iostream&#include&cstdio&#include&cstring&#include&cstdlib&#include&map&#include&ctime&#include&vector&#include&set&#include&cmath&#include&algorithm&#define inf #define ll long longusing namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch&'0'||ch&'9'){if(ch=='-')f=-1;ch=getchar();} while(ch&='0'&&ch&='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int n,cnt,S,L,U,root,lim;double ans;struct edge{int to,next,v;}e[200005];int last[200005];int size[100005],fa[100005],f[100005],deep[100005];int q[100005],dq[100005];bool mark[100005];double dis[100005],mx[100005];void insert(int u,int v,int w){ e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;}void getroot(int x,int fa){ size[x]=1;f[x]=0; for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa&&!mark[e[i].to])
getroot(e[i].to,x);
size[x]+=size[e[i].to];
f[x]=max(f[x],size[e[i].to]);
} f[x]=max(f[x],S-size[x]); if(f[x]&=f[root])root=x;}bool jud(int rt,double M){ int up=0; for(int t=last[rt];t;t=e[t].next) {
if(mark[e[t].to])continue;
int head=0,tail=1;
q[0]=e[t].to;
fa[e[t].to]=root;deep[e[t].to]=1;
dis[e[t].to]=(double)e[t].v-M;
while(head!=tail)
int now=q[head];head++;
for(int i=last[now];i;i=e[i].next)
if(e[i].to!=fa[now]&&!mark[e[i].to])
q[tail]=e[i].to;
fa[e[i].to]=now;deep[e[i].to]=deep[now]+1;
dis[e[i].to]=dis[now]+e[i].v-M;
int l=1,r=0,now=up;
for(int i=0;i&tail;i++)
int x=q[i];
while(deep[x]+now&=L&&now&=0)
while(l&=r&&mx[dq[r]]&mx[now])r--;
dq[++r]=now;
while(l&=r&&deep[x]+dq[l]&U)l++;
if(l&=r&&dis[x]+mx[dq[l]]&=0)return 1;
for(int i=up+1;i&=deep[q[tail-1]];i++)mx[i]=-inf;
for(int i=0;i&tail;i++)
int x=q[i];
mx[deep[x]]=max(mx[deep[x]],dis[x]);
up=max(up,deep[q[tail-1]]); } return 0;}void cal(int x){ double l=ans,r=lim,mid; while(r-l&0.0001) {
mid=(l+r)/2;
if(jud(x,mid))l=mid;
else r=mid; } ans=l;}void solve(int x){ cal(x); mark[x]=1; for(int i=last[x];i;i=e[i].next)
if(!mark[e[i].to])
root=0;S=size[e[i].to];
getroot(e[i].to,0);
if(size[e[i].to]&L)
solve(root);
}}int main(){ freopen("rebuild.in","r",stdin); freopen("rebuild.out","w",stdout); n=read();L=read();U=read(); for(int i=1;i&n;i++) {
int u=read(),v=read(),w=read();
insert(u,v,w);
lim=max(lim,w); } f[0]=n; root=0;S=n; getroot(1,0); solve(root); printf("%.3lf",ans); return 0;}
2397095 "自己选择的路,跪着也要走完"
图包度娘盘340*240(9M) h7wf
WP Cumulus Flash tag cloud by
本站热门430528362389229122262109207920172004196919231855182518081807Myfriends