【BZOJ 4326】【NOIP2015】运输计划
2018-06-17 23:38:00来源:未知 阅读 ()
http://www.lydsy.com/JudgeOnline/problem.php?id=4326
题目描述
公元2044年,人类进入了宇宙纪元。
国有个星球,还有条双向航道,每条航道建立在两个星球之间,这条航道连通了国的所有星球。
小掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从号星球沿最快的宇航路径飞行到号星球去。显然,飞船驶过一条航道是需要时间的,对于航道,任意飞船驶过它所花费的时间为,并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新,国国王同意小的物流公司参与国的航道建设,即允许小把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。在虫洞的建设完成前小的物流公司就预接了个运输计划。在虫洞建设完成后,这个运输计划会同时开始,所有飞船一起出发。当这个运输计划都完成时,小的物流公司的阶段性工作就完成了。如果小可以自由选择将哪一条航道改造成虫洞,试求出小的物流公司完成阶段性工作所需要的最短时间是多少?
输入格式
第一行包括两个正整数,表示国中星球的数量及小公司预接的运输计划的数量,星球从1到编号。接下来行描述航道的建设情况,其中第行包含三个整数 和,表示第条双向航道修建在与两个星球之间,任意飞船驶过它所花费的时间为。数据保证 。接下来行描述运输计划的情况,其中第行包含两个正整数和,表示第个运输计划是从号星球飞往号星球。
输出格式
输出文件只包含一个整数,表示小的物流公司完成阶段性工作所需要的最短时间。
输入样例
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
输出样例
11
数据范围
题解
二分路径交
利用 求出每条路径的长度,二分答案 ,对于所有路径 的路径都至少需要删掉一条边,最优方案一定是删去这些路径交的最长边,即 的路径都经过的一条最长边。
考虑如何求出路径交: 表示点 到 这一条边经过的路径数,对于一条从 到 的路径,将 和 均,,向上求和即可。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #define depth 21 #define N 300005 using namespace std; int n,m,tot,ans; int anc[N][22],a[N],b[N],d[N],lca[N],last[N],dep[N],fa[N],sum[N],v[N],dis[N]; stack<int> s; struct hh { int to,next,w; }e[N<<1]; int read() { int ret=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c)){ret=(ret<<1)+(ret<<3)+c-'0';c=getchar();} return ret; } void add(int fr,int to,int w) { e[++tot].to=to; e[tot].w=w; e[tot].next=last[fr]; last[fr]=tot; } void bfs(int root) { int i,j,now; s.push(root); dep[root]=1; for(i=0;i<=depth;i++) anc[root][i]=root; while(!s.empty()) { now=s.top();s.pop(); if(now!=root) for(i=1;i<=depth;i++) anc[now][i]=anc[anc[now][i-1]][i-1]; for(i=last[now];i;i=e[i].next) if(!dep[e[i].to]) { dep[e[i].to]=dep[now]+1; anc[e[i].to][0]=now; fa[e[i].to]=now; v[e[i].to]=e[i].w; dis[e[i].to]=dis[now]+e[i].w; s.push(e[i].to); } } } void swim(int &x,int h) { int i; for(i=0;h;i++) { if(h&1) x=anc[x][i]; h/=2; } } int get_lca(int x,int y) { int i; if(dep[x]>dep[y]) swap(x,y); if(dep[x]!=dep[y]) swim(y,dep[y]-dep[x]); if(x==y) return x; while(true) { for(i=0;anc[x][i]!=anc[y][i];i++); if(i==0) return anc[x][0]; i--;x=anc[x][i];y=anc[y][i]; } } void work(int now) { int i,j; for(i=last[now];i;i=e[i].next) if(e[i].to!=fa[now]) { work(e[i].to); sum[now]+=sum[e[i].to]; } } bool check(int lim) { int i,j,cnt=0,t=0; for(i=1;i<=n;i++) sum[i]=0; for(i=1;i<=m;i++) if(d[i]>lim) { cnt++; t=max(t,d[i]-lim); sum[a[i]]++;sum[b[i]]++; sum[lca[i]]-=2; } work(1); for(i=1;i<=n;i++) if(sum[i]==cnt&&v[i]>=t) return true; return false; } int main() { int i,j,u,v,w,l,r,mid; n=read();m=read(); for(i=1;i<=n-1;i++) { u=read();v=read();w=read(); add(u,v,w);add(v,u,w); } bfs(1); for(i=1;i<=m;i++) { a[i]=read();b[i]=read(); lca[i]=get_lca(a[i],b[i]); d[i]=dis[a[i]]+dis[b[i]]-(dis[lca[i]]<<1); } l=0,r=d[1]; for(i=2;i<=m;i++) r=max(r,d[i]); ans=99999999; while(l<=r) { mid=(l+r)>>1; if(check(mid)) ans=min(ans,mid),r=mid-1; else l=mid+1; } printf("%d",ans); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash