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运输计划”的5个回复

  1. Levitra Esercizi Di Kegel Malegra cheapest cialis 20mg Cephalexin Can You Get At Walgreens Buy Synthroid Online No Prescriptionbuy Tadacip 20 Tomar Viagra O Cialis Next Day Express Delivery For Viagra Viagra Online In Italia Chipest cialis How To Buy Levaquin Overseas Comprar Cialis Y Priligy How To Last Longer During Cephalexin 500mg Effect How To Use Kamagra Oral Jelly india pharmacy zoloft Costo Viagra Ricetta Propecia Conseguenze Tamoxifen Online Pharmacy Purity Solutions Tadalafil Review Viagra Non Generic Order Propecia Online Mastercard cialis without prescription Canadian Online Pharmacy

  2. Propecia Cost Months Generique Du Cialis kamagra 100 mg oral jelly Levitra Ablaufdatum Bull 100tablets Ciprofloxacine Diarrhee Discount Nexium Prescription viagra Effet Cytotec Contraception Amoxicillin Without Rx Levitra Vardenafil Hydrochloride Avamigran Con Receta Comprar Propecia Propecia Esteroides viagra Achat Propranolol Levitra Generique En Officine Sex Med Man Best Generic Viagra Pharmacies Online Levitra viagra generico consegna rapida Viagra 8 Mg Acheter Levitra En Valais Keflex Urinary Tract Infections Bacteria Resistance canadian pharmacy cialis 20mg Levitra Kaufen Austria Viagra Et Angor Eosinophillia Amoxicillin

  3. I know this if off topic but I’m looking into starting my own weblog
    and was wondering what all is needed to get set up? I’m assuming having
    a blog like yours would cost a pretty penny?
    I’m not very internet savvy so I’m not 100% positive.
    Any recommendations or advice would be greatly appreciated.

    Cheers

发表评论