BZOJ 1758: [Wc2010]重建计划 [暂时放弃]
时间： 22:22:12
&&&& 阅读：18
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&
今天晚上思维比较乱，以后再写写吧#include &iostream&
#include &cstdio&
#include &cstring&
#include &algorithm&
using namespace
typedef long long
const int N=1e5+5,INF=1e9+5;
double eps=1e-4;
inline int read(){
char c=getchar();int x=0,f=1;
while(c&‘0‘||c&‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c&=‘0‘&&c&=‘9‘){x=x*10+c-‘0‘;c=getchar();}
return x*f;
int n,L,U,a,b;
double w,maxVal,
struct edge{
inline void ins(int u,int v,double w){
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=
int f[N],size[N],all,vis[N],
void dfsRt(int u,int fa){
size[u]=1;f[u]=0;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]||v==fa) continue;
dfsRt(v,u);
size[u]+=size[v];
f[u]=max(f[u],size[v]);
f[u]=max(f[u],all-size[u]);
if(f[u]&f[root]) root=u;
int q[N],head,tail,deep[N];
double val[N],mx[N];
bool visit[N];
void bfs(double g){
while(head&=tail){
int u=q[head++];
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]) continue;
if(!visit[v]){
visit[v]=1;
q[++tail]=v;
deep[v]=deep[u]+1;
val[v]=val[u]+e[i].w-g;
double c[N];
bool dp(int n){//printf("dp %d %d\n",n,n+m);
if(m+n&L) return false;
head=1;tail=0;
int l=max(L-n,1),r=U-n;
for(int i=l;i&=r&&i&=m;i++){//printf("ins %d\n",i);
while(head&=tail&&c[q[tail]]&c[i]) tail--;
q[++tail]=i;
for(int i=n;i&=1;i--){//printf("i %d %lf\n",i,mx[i]);
int l=L-i,r=U-i;//printf("lala %d %d\n",l,r);
while(head&=tail&&q[head]&l) head++;
while(head&=tail&&c[r]&c[q[tail]]) tail--;
q[++tail]=r;
//printf("qqq %d %d
%lf\n",head,tail,c[q[head]]);
if(head&=tail&&c[q[head]]+mx[i]&=0) return true;
return false;
bool check(int u,double g){//printf("\ncheck %d %lf\n",u,g);
for(int i=1;i&=m;i++) c[i]=-INF;m=0;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(vis[v]) continue;
//printf("\nv %d\n",v);
head=1;tail=0;
q[++tail]=v;
deep[v]=1;val[v]=e[i].w-g;
//for(int i=1;i&i++) //printf("%lf ",val[i]);puts("");
for(int i=1;i&=deep[q[tail]];i++) mx[i]=-INF;
for(int i=1;i&=i++)
id=q[i],mx[deep[id]]=max(mx[deep[id]],val[id]),visit[id]=0;
//for(int i=1;i&=maxDi++) printf("mx %d %lf \n",i,mx[i]);
if(dp(deep[q[tail]])) return true;
m=max(m,deep[q[tail]]);
for(int i=1;i&=deep[q[tail]];i++) c[i]=max(c[i],mx[i]);
return false;
void dfsSol(int u){//printf("dfsSol %d\n",u);if(u!=1)
double l=ans,r=maxV//printf("lr %lf %lf\n\n",l,r);
while(r-l&eps){
double mid=(l+r)/2;
if(check(u,mid)) l=
ans=max(ans,l);
for(int i=h[u];i;i=e[i].ne)
if(!vis[e[i].v]){
root=0;all=size[e[i].v];
if(size[e[i].v]&L) continue;
dfsRt(e[i].v,0);
dfsSol(root);
int main(){
freopen("in","r",stdin);
//freopen("out","w",stdout);
n=read();L=read();U=read();
for(int i=1;i&n;i++)
a=read(),b=read(),w=read(),ins(a,b,w),maxVal=max(maxVal,w);
root=0;f[0]=INF;all=n;
dfsRt(1,0);
dfsSol(root);
printf("%.3lf",ans);
&标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文：/candy99/p/6498557.html
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！