NOIP2016运输计划

废话——

当Oveln看到这题的第一眼之后的想法竟然是【完蛋了还有四十多天退役////

讲道理是昨天晚上看了一眼题目就回寝室了

然后今天的历史课想的……(雨滋会不会打死我……

晚上看看网上的题解居然没有我这种解法??

赶紧写篇题解水一下(

题目

公元 2044 20442044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n−1条双向航道,每条航道建立在两个星球之间,这 n−1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

题解

思考……

首先我们分析一下题目

给出一棵n个点的树,和m条在树上的链,求使一条边的长度为0之后最长的链的长度最短,并求出最短的值

嗯……仿佛并没有什么想法

然后oveln想到了二分答案——

二分一个值x,求是否可以使所有的链长度小于x

另m1为小于x的链的条数

那么开始的时候m1条链长度小于x的链就可以不用考虑了

对于大于x的(m-m1)条边,需要找到一条边c

对于边c条件有两个:在这些链上面,并且这条边c长度大于(最长的链-x)

这样才能保证m条边的最长长度小于x

不思考了

问题剩下一个,如何找到边c

边c肯定在所有的链的公共部分上,我们可以把c设定为公共部分最长的一条边(因为这样必定是最优的),而这公共部分肯定也是一条链……

问题变成了——如何求两条链的公共链

Oveln在历史课上思考了半节课差点被雨滋盯死之后进行了分类讨论

两种情况

(灵魂画手Oveln上线&&)A1A2,B1B2分别是两条链的两个端点

Lca(A1,A2)==Lca(B1,B2)

对于这种情况,公共链的两个端点显然是,Lca(A1,B1),Lca(A2,B2)

Lca(A1,A2)!=Lca(B1,B2)

对于这种情况,公共链的两个端点显然是,Lca(A1,B1),Lca(B1,B2)

某:这么简单的两种分类Oveln你居然想了半节课!!!

当然不是那么简单了……因为给出的链的两个端点不可能刚好按照图上的那样排列

比如有时候会变成——

这个样子,那么需要确定两条链的两个端点的顺序才能更好的写程序(省代码

关于这个问题

对于第一个情况,很简单,如果Lca(A1,B1)==Lca(A1,A2)的话交换一下B1,B2就行了

对于第二个情况,观察一下特征之后,发现只有当Dep[Lca(A1,B1)]>Dep[Lca(B1,B2)]的时候那个Lca(A1,B1)才是我们需要的,那么枚举一下四种情况就好了

详见代码 其实是写不清楚

问题来了

Oveln算了一下时间复杂度

log(n)mlog(n)=log(n)^2log(m)

或许……肯定会Tle

Oveln这是陷入了绝望

再想想……二分的必要好像已经没有了!!

只要一开始的时候将m条链按照链长排序之后求1到i的公共链的即可

而1到i的公共链可以通过求1到i-1的公共链与第i条链的公共链求出

所以每次更新答案,Ans=max(Ans,Max(第i+1条链的长度,第1条链的长度-1到i的公共链中最长的边))

时间复杂度mlogn

完美

代码


\#include <cstdio> #include <cctype> #include <algorithm> #define maxn 300005 #define maxm 300005 inline unsigned int Log2(unsigned int x){//黑科技Log2效率O(1) ​ unsigned int ret; ​ __asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x)); ​ return ret; } inline int read() { ​ int x=0,f=0; ​ char ch=getchar(); ​ while (!isdigit(ch)) f^=(ch=='-'),ch=getchar(); ​ while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); ​ if (f) return -x;return x; } inline void OPENFILE() { #ifndef ONLINE_JUDGE ​ freopen("data.in","r",stdin); ​ freopen("data.out","w",stdout); #endif } int lnk[maxn],nxt[maxn*2],son[maxn*2],w[maxn*2],tot; int n,m; struct ad { ​ int p[2],w; ​ inline bool operator ==(const ad y) {return (p[0]==y.p[0]&&p[1]==y.p[1])||(p[0]==y.p[1]&&p[1]==y.p[0]);} }a[maxm],now; int dep[maxn],pre[maxn][32],f[maxn][32],s[maxn][32]; int ans; inline void swap(ad &x,ad &y) {ad t=x;x=y,y=t;} inline void swap(int &x,int &y) {x^=y,y^=x,x^=y;} inline void Add_e(int x,int y,int z) {son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot,w[tot]=z;} inline int max(int x,int y) {if (x>y) return x;return y;} inline int min(int x,int y) {if (x<y) return x;return y;} inline bool cmp(ad x,ad y) {return x.w>y.w;} void Dfs(int x=1) {//Lca的预处理,自我感觉这么写特别棒……然而zxb仍然不改邪归正××× ​ for (int i=1,ed=Log2(dep[x]);i<=ed;i++) ​ pre[x][i]=pre[pre[x][i-1]][i-1], ​ f[x][i]=max(f[x][i-1],f[pre[x][i-1]][i-1]), ​ s[x][i]=s[x][i-1]+s[pre[x][i-1]][i-1]; ​ for (int i=lnk[x];i;i=nxt[i]) if (!dep[son[i]]) { ​ dep[son[i]]=dep[x]+1,pre[son[i]][0]=x,s[son[i]][0]=f[son[i]][0]=w[i]; ​ Dfs(son[i]); ​ } } int Lca(int x,int y) {//求公共祖先 ​ if (dep[x]<dep[y]) x^=y,y^=x,x^=y; ​ int d=dep[x]-dep[y]; ​ for (int i=Log2(d);i>=0;i--) if ((1<<i)&d) ​ x=pre[x][i]; ​ if (x^y) { ​ for (int i=Log2(dep[x]);i>=0;i--) if (pre[x][i]^pre[y][i]) ​ x=pre[x][i],y=pre[y][i]; ​ x=pre[x][0],y=pre[y][0]; ​ } ​ return x; } int Lcaw(int x,int y) {//求x到y的链长 ​ if (dep[x]<dep[y]) x^=y,y^=x,x^=y; ​ int d=dep[x]-dep[y],ret=0; ​ for (int i=Log2(d);i>=0;i--) if ((1<<i)&d) ​ ret+=s[x][i],x=pre[x][i]; ​ if (x^y) { ​ for (int i=Log2(dep[x]);i>=0;i--) if (pre[x][i]^pre[y][i]) ​ ret+=s[x][i]+s[y][i],x=pre[x][i],y=pre[y][i]; ​ ret+=s[x][0]+s[y][0],x=pre[x][0],y=pre[y][0]; ​ } ​ return ret; } int Lcamx(int x,int y) {//求x到y的最大的边 ​ if (dep[x]<dep[y]) x^=y,y^=x,x^=y; ​ int d=dep[x]-dep[y],ret=0; ​ for (int i=Log2(d);i>=0;i--) if ((1<<i)&d) ​ ret=max(ret,f[x][i]),x=pre[x][i]; ​ if (x^y) { ​ for (int i=Log2(dep[x]);i>=0;i--) if (pre[x][i]^pre[y][i]) ​ ret=max(ret,max(f[x][i],f[y][i])),x=pre[x][i],y=pre[y][i]; ​ ret=max(ret,max(f[x][0],f[y][0])),x=pre[x][0],y=pre[y][0]; ​ } ​ return ret; } ad Make(ad x,ad y) {求x链与y链的公共链 ​ if (x==y) return x;//注意这个 ​ ad ret=(ad){0,0}; ​ int Lcax=Lca(x.p[0],x.p[1]),Lcay=Lca(y.p[0],y.p[1]); ​ if (dep[Lcax]<dep[Lcay]) swap(x,y),swap(Lcax,Lcay); ​ if (Lcax==Lcay) { ​ if (Lca(x.p[0],y.p[0])==Lcax) swap(y.p[0],y.p[1]); ​ ret=(ad){Lca(x.p[0],y.p[0]),Lca(x.p[1],y.p[1])}; ​ }else { ​ bool fg=0; ​ for (int i=0;i<2;i++) ​ for (int j=0;j<2;j++) if (dep[Lca(x.p[i],y.p[j])]>dep[Lcax]) { ​ if (i) swap(x.p[0],x.p[1]); ​ if (j) swap(y.p[0],y.p[1]); ​ fg=1;break; ​ } ​ if (!fg) return (ad){-1,-1}; ​ ret=(ad){Lca(x.p[0],y.p[0]),Lcax}; ​ } ​ return ret; } int main() { ​ OPENFILE(); ​ n=read(),m=read(); ​ for (int i=1,x,y,z;i<n;i++) ​ x=read(),y=read(),z=read(),Add_e(x,y,z),Add_e(y,x,z); ​ for (int i=1;i<=m;i++) ​ a[i]=(ad){read(),read(),0}; ​ dep[1]=1,Dfs(); ​ for (int i=1;i<=m;i++) a[i].w=Lcaw(a[i].p[0],a[i].p[1]); ​ std::sort(a+1,a+1+n,cmp); ​ now=a[1],ans=max(a[2].w,a[1].w-Lcamx(now.p[0],now.p[1])); ​ for (int i=2;i<=m;i++) { ​ now=Make(now,a[i]); ​ if (now.p[0]==-1) break; ​ ans=min(ans,max(a[1].w-Lcamx(now.p[0],now.p[1]),a[i+1].w)); ​ } ​ printf("%d\n",ans); ​ return 0; }

“NOIP2016运输计划”的一个回复

发表评论

电子邮件地址不会被公开。