运输计划

痛定思痛。 2021-11-29 21:44 271阅读 0赞

# [传送门][Link 1] #

### 解法: ###

首先要学会求 树的最近公共祖先(LCA)

没用树剖  
用了一个经常可以代替树剖的方法  
树上差分 这个方法很优秀 一定要掌握

首先 有了lca 就可以求树上两点间长度  
设 \\(d\[x\]\\) 为 \\(x\\) 到 根节点 的距离  
则 \\(u\\),\\(v\\) 间距离为 \\(d\[u\]+d\[v\]-2\*d\[lca(u,v)\]\\)

同时可以实现差分  
设 \\(ver\[x\]\\) 为 \\(x\\) 的差分数组  
对于 \\(u\\),\\(v\\) 连边 覆盖原图边的差分处理 \\(ver\[u\]++,ver\[v\]++,ver\[lca(u,v)\]-=2\\)  
在进行一次dfs就求到 **每个点x到父节点的边** 被覆盖的次数ver\[x\]

二分答案

对于每个\\(u\\),\\(v\\)若距离>二分的值  
说明此时要在其覆盖的边中减去一条满足条件的  
差分处理

设此时有cnt个路径要删边  
那么能达到此时二分答案则**必须有一条边被所有路径覆盖**  
即dfs后 存在\\(ver\[x\]==cnt\\)且此时删去改边后 **最长的一条路径也要不大于此时答案**  
此答案才可行

最后二分求出的最大可行值即为答案

### 代码: ###

第一种 倍增法求lca O(nlogn+mlogm+(n+m)logSum) 可能会被卡掉一两个点 开O2能过

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<map> #define inf 2000000000 #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define dwn(i,a,b) for(int i=(a);i>=(b);--i) using namespace std; typedef long long ll; int n,m,sum=0,ans; int root=1,dep[300010],f[300010][20],lg2[300010],d[300010],ver[300010]; int tot=1,head[300010]; struct node { int u,v,lca,dis; }qu[300010]; struct EDGE { int to,nxt,d; }edge[600010]; queue<int> que; inline void add(int u,int v,int d) { edge[++tot].to=v; edge[tot].nxt=head[u]; edge[tot].d=d; head[u]=tot; } inline void bfs() { dep[root]=1; que.push(root); while(!que.empty()) { int x=que.front();que.pop(); for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(dep[y]) continue; f[y][0]=x;dep[y]=dep[x]+1;d[y]=d[x]+edge[i].d; rep(j,1,lg2[dep[y]]) { f[y][j]=f[f[y][j-1]][j-1]; } que.push(y); } } } inline int lca(int x,int y) { if(dep[x]>dep[y]) swap(x,y); dwn(i,lg2[dep[y]-dep[x]],0) if(dep[f[y][i]]>=dep[x]) y=f[y][i]; if(x==y) return x; dwn(i,lg2[dep[x]],0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } void dfs(int x) { for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(dep[x]>dep[y]) continue; dfs(y); ver[x]+=ver[y]; } } bool check(int mid) { memset(ver,0,sizeof(ver)); int cnt=0,maxn=0; rep(i,1,m) { if(qu[i].dis>mid) { cnt++; ver[qu[i].u]++,ver[qu[i].v]++,ver[qu[i].lca]-=2; maxn=max(maxn,qu[i].dis-mid); } } if(cnt==0) return 1; dfs(root); rep(i,1,n) if(i!=root&&ver[i]==cnt&&d[i]-d[f[i][0]]>=maxn) return 1; return 0; } int main() { scanf("%d%d",&n,&m); rep(i,2,n) { lg2[i]=lg2[i>>1]+1; } rep(i,1,n-1) { int u,v,d; scanf("%d%d%d",&u,&v,&d); add(u,v,d),add(v,u,d); sum+=d; } bfs(); rep(i,1,m) { int u,v; scanf("%d%d",&u,&v); qu[i].lca=lca(u,v); qu[i].dis=d[u]+d[v]-2*d[qu[i].lca]; qu[i].u=u,qu[i].v=v; } int l=0,r=sum; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } printf("%d\n",ans); return 0; }

第二种 tarjan的lca算法 O(n+m+(n+m)logSum) 相对快一些 不用O2过

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<map> #define inf 2000000000 #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define dwn(i,a,b) for(int i=(a);i>=(b);--i) using namespace std; typedef long long ll; typedef pair<int,int> P; int n,m,sum=0,ans; int root=1,d[300010],fa[300010],ver[300010]; int tot=1,head[300010]; int v[300010],par[300010]; struct node { int u,v,lca,dis; }qu[300010]; struct EDGE { int to,nxt,d; }edge[600010]; queue<int> que; vector<P> ques[300010]; inline void add(int u,int v,int d) { edge[++tot].to=v; edge[tot].nxt=head[u]; edge[tot].d=d; head[u]=tot; } inline void bfs() { que.push(root); fa[root]=root; while(!que.empty()) { int x=que.front();que.pop(); for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(fa[y]) continue; d[y]=d[x]+edge[i].d; fa[y]=x; que.push(y); } } } int get(int x) { if(x==par[x]) return x; return par[x]=get(par[x]); } void tarjan(int x) { v[x]=1; for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(v[y]) continue; tarjan(y); par[y]=x; } for(int i=0;i<ques[x].size();++i) { if(v[ques[x][i].first]==2) qu[ques[x][i].second].lca=get(ques[x][i].first); } v[x]=2; } void dfs(int x) { for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(fa[y]!=x) continue; dfs(y); ver[x]+=ver[y]; } } bool check(int mid) { memset(ver,0,sizeof(ver)); int cnt=0,maxn=0; rep(i,1,m) { if(qu[i].dis>mid) { cnt++; ver[qu[i].u]++,ver[qu[i].v]++,ver[qu[i].lca]-=2; maxn=max(maxn,qu[i].dis-mid); } } if(cnt==0) return 1; dfs(root); rep(i,1,n) if(i!=root&&ver[i]==cnt&&d[i]-d[fa[i]]>=maxn) return 1; return 0; } int main() { scanf("%d%d",&n,&m); rep(i,1,n-1) { int u,v,d; scanf("%d%d%d",&u,&v,&d); add(u,v,d),add(v,u,d); sum+=d; } bfs(); rep(i,0,n) par[i]=i; rep(i,1,m) { int u,v; scanf("%d%d",&u,&v); qu[i].u=u,qu[i].v=v; if(u==v) qu[i].lca=u,qu[i].dis=0; else ques[u].push_back(P(v,i)),ques[v].push_back(P(u,i)); } tarjan(root); rep(i,1,m) qu[i].dis=d[qu[i].u]+d[qu[i].v]-2*d[qu[i].lca]; int l=0,r=sum; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/MYsBlogs/p/11116687.html

[Link 1]: https://www.luogu.org/problemnew/show/P2680