P2680 运输计划 题目
这道题如果是看的我的树上差分来的,那么肯定一看题目就可以想到树上差分.
至于这是怎么想到的,一步一步来:
1.n有300000,不可能暴力枚举每一条边
2.因为我们要使运输时间的最大值最小,所以,考虑二分答案(做多了之后的习惯(其实也就是突然的灵感,不是必然......))
3.既然二分了答案,暂且把我们二分的答案变量名叫 lim ,考虑On的check():
想到每次把超过lim(跑LCA求运输计划的时间)的运输计划全部要考虑删边(显然),并且这些计划都必须要删一条公共边(也是显然,加虫洞就相当于把边权变为0,姑且叫做删边把),这就可以考虑差分了,把超过lim的计划全部差分进去,统计一下差分数组,枚举所有计划都经过的边(也就是差分数组==超过lim的计划数),看看最大的运输代价减去这个边权(相当于把它变为0,显然)是否小于lim, return1/0(显然最大值都小于lim了,所有的都小于lim了); 完成check()!
上代码:
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iomanip> #include<ctime> #include<queue> #include<stack> #define rg register #define lst long long #define N 300050 using namespace std; int n,m,cnt,ans,maxn,le,ri; struct EDGE{ int to,v,nxt; }edge[N<<1]; struct ROAD{ int fm,to,v; }road[N]; int head[N],back[N]; int cf[N]; int deep[N],fa[N]; int f[N][25],g[N][25]; inline int read() { rg int s=0,m=1;rg char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')m=-1,ch=getchar(); while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar(); return s*m; } inline void add(rg int p,rg int q,rg int o) { edge[++cnt].to=q,edge[cnt].v=o; edge[cnt].nxt=head[p]; head[p]=cnt; } void dfs(rg int now,rg int fm,rg int dep,rg int s)//dfs预处理倍增LCA { fa[now]=fm,deep[now]=dep; f[now][0]=fm;g[now][0]=s; for(rg int i=1;i<=20;++i) { f[now][i]=f[f[now][i-1]][i-1]; g[now][i]=g[f[now][i-1]][i-1]+g[now][i-1]; } for(rg int i=head[now];i;i=edge[i].nxt) { rg int qw=edge[i].to; if(qw!=fm) { back[qw]=i; dfs(qw,now,dep+1,edge[i].v); } } } inline int LCA(rg int x,rg int y,rg int op)//倍增跳LCA { rg int res=0; if(deep[x]<deep[y])swap(x,y); while(deep[x]>deep[y])//跳到同样深度 for(rg int i=20;i>=0;--i) if(deep[f[x][i]]>=deep[y])res+=g[x][i],x=f[x][i]; while(x!=y) { for(rg int i=20;i>=0;--i) if(f[x][i]!=f[y][i]) res+=g[x][i]+g[y][i],x=f[x][i],y=f[y][i]; if(fa[x]==fa[y])res+=g[x][0]+g[y][0],x=y=fa[x]; } if(!op)return res; else return x; } inline void Insert(rg int p,rg int q)//差分 { rg int lca=LCA(p,q,1); cf[p]++,cf[q]++,cf[lca]-=2; } void sum(rg int now)//统计差分数组 { for(rg int i=head[now];i;i=edge[i].nxt) { rg int qw=edge[i].to; if(qw!=fa[now]) { sum(qw); cf[now]+=cf[qw]; } } } inline int check(rg int lim)//如解析,check() { rg int ss=0,Max=0; for(rg int i=1;i<=n;++i)cf[i]=0; for(rg int i=1;i<=m;++i) { if(road[i].v>lim) { Max=max(Max,road[i].v); ss++,Insert(road[i].fm,road[i].to); } } sum(0); for(rg int i=1;i<=n;++i) if(cf[i]==ss&&Max-edge[back[i]].v<=lim)return 1; return 0; } int main() { n=read(),m=read(); for(rg int i=1;i<n;++i) { rg int p=read(),q=read(),o=read(); add(p,q,o),add(q,p,o); } //读入边的信息 dfs(1,0,1,0); for(rg int i=1;i<=m;++i) { rg int p=read(),q=read(); road[i].fm=p,road[i].to=q,road[i].v=LCA(p,q,0); ri=max(ri,road[i].v); } add(0,1,0);//没事干加了一个 0->1 的边,感觉比较踏实(0的父亲是1)...无语... while(le<=ri)//二分 { rg int mid=(ri+le)>>1; if(check(mid))ans=mid,ri=mid-1; else le=mid+1; } printf("%d ",ans); return 0; }