博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
题解——洛谷 P2680 NOIP提高组 2015 运输计划
阅读量:5970 次
发布时间:2019-06-19

本文共 3214 字,大约阅读时间需要 10 分钟。

树上差分加上二分答案

详细题解待填坑

#include 
#include
#include
using namespace std;const int MAXlog = 20;const int MAXM = 711001;const int MAXN = 400001;int dep[MAXN],jump[MAXN][MAXlog+2];int lcav[MAXM],cf[MAXN],fw[MAXN],lent[MAXN];int uline[MAXM],vline[MAXM],wline[MAXM];int cnt=0,u[MAXN*2],v[MAXN*2],w[MAXN*2],first[MAXN*2],next[MAXN*2];int n,m;void addline(int ux,int vx,int i){ uline[i]=ux; vline[i]=vx; wline[i]=lent[ux]+lent[vx]-2*lent[lcav[i]];}void addedge(int ux,int vx,int wx){ cnt++; u[cnt]=ux; v[cnt]=vx; w[cnt]=wx; next[cnt]=first[ux]; first[ux]=cnt;}void dfs(int u,int f){// printf("u=%d f=%d\n",u,f); dep[u]=dep[f]+1; jump[u][0]=f;// printf("u=%d j=0 jump=%d\n",u,jump[u][0]); for(int i=1;i<=MAXlog;i++){ jump[u][i]=jump[jump[u][i-1]][i-1];// printf("u=%d j=%d jump=%d\n",u,i,jump[u][i]); } for(int i=first[u];i;i=next[i]) if(v[i]!=f) dfs(v[i],u);}void dfs2(int u,int f,int wk){ fw[u]=wk; lent[u]=lent[f]+wk; for(int i=first[u];i;i=next[i]) if(v[i]!=f) dfs2(v[i],u,w[i]);}int lca(int x,int y){ if(dep[y]>dep[x]) swap(x,y); for(int i=MAXlog;i>=0;i--) if(dep[x]-(1<
=dep[y]) x=jump[x][i]; if(x==y) return x; for(int i=MAXlog;i>=0;i--) if(jump[x][i]!=jump[y][i]){ x=jump[x][i]; y=jump[y][i]; } return jump[x][0];}void runcf(int l){ cf[uline[l]]++; cf[vline[l]]++; cf[lcav[l]]-=2;}int maxlen=0;void calcf(int u,int f,int num){ for(int i=first[u];i;i=next[i]){ if(v[i]==f) continue; calcf(v[i],u,num); cf[u]+=cf[v[i]]; } if(cf[u]==num&&fw[u]>maxlen) maxlen=fw[u];}bool check(int ans){ int inq=0; int maxchain=0; maxlen=0;// printf("!ok\n"); memset(cf,0,sizeof(cf)); for(int i=1;i<=cnt;i++) if(wline[i]>ans){ runcf(i); inq++; if(wline[i]>maxchain) maxchain=wline[i]; } calcf(1,0,inq);// printf("*ok\n"); if(maxchain-maxlen<=ans) return true; else return false;}int main(){ scanf("%d %d",&n,&m); int maxt=0; for(int i=1;i<=n-1;i++){ int a,b,t; scanf("%d %d %d",&a,&b,&t); addedge(a,b,t); addedge(b,a,t); maxt=max(maxt,t); } dep[0]=-1; dfs(1,0); dfs2(1,0,0); int maxline=0; for(int i=1;i<=m;i++){ int um,vm; scanf("%d %d",&um,&vm);// if(jump[5][0]!=3)// printf("!\n"); lcav[i]=lca(um,vm); addline(um,vm,i); if(wline[i]>maxline) maxline=wline[i]; } /*for(int i=0;i<=n;i++){ for(int j=0;j<=MAXlog;j++) printf("jump[%d][%d]=%d \n",i,j,jump[i][j]); printf("\n"); }*/ /*for(int i=1;i<=m;i++){ printf("u=%d v=%d lca=%d len=%d\n",uline[i],vline[i],lcav[i],wline[i]); }*/ int l=maxline-maxt,r=maxline+1; while(l
>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d",r); return 0;}

 

转载于:https://www.cnblogs.com/dreagonm/p/9433524.html

你可能感兴趣的文章
Shiro内置的FilterChain
查看>>
Oracle中group by用法
查看>>
epoll 示例
查看>>
Django之Form组件
查看>>
JavaScript笔记
查看>>
Redis进阶实践之二如何在Linux系统上安装安装Redis
查看>>
源码编译 MySQL 完整配置选项
查看>>
从网上搜索到的虚拟化笔记
查看>>
我的友情链接
查看>>
jq实现跳转404跳转,原生js实现跳转404跳转
查看>>
配置maven nenux仓库
查看>>
js setTimeout()的使用
查看>>
Hadoop和大数据:60款顶级开源工具
查看>>
高可用集群中的选举机制
查看>>
江苏理工学院计算学院实验教学管理系统[.NET项目]
查看>>
bash编程总结
查看>>
Android中进程间通讯 AIDL
查看>>
rcp errata
查看>>
Kotlin 与 Java 8 的重要新特性以及 Java 9、10 的发展规划
查看>>
垂直居中实现方式总结
查看>>