Codeforces 1253 F. Cheap Robot —— 想法，dijkstra+kruskal重构树+并查集+树链剖分+lca，有丶东西

本文主要是介绍Codeforces 1253 F. Cheap Robot —— 想法，dijkstra+kruskal重构树+并查集+树链剖分+lca，有丶东西，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一张大小为n的图，并且点1~k是充电站。有q个询问，每次询问你从a走到b最少需要的电池大小为多少。
假设你当前电量为c，当走过一个权值为w的边时，你的点会变成c-w，如果这个点是充电站，那么你的电量会便会变回电池容量。
问你你每次需要的电池容量最小是多少。

题解：

有一说一，这道题很厉害。
首先先用dijkstra找到每个点距离它最近的充电站的距离，然后的话我们可以知道，如果一条边要用到，当且仅当$dis[x]+dis[y]+e[i].w\le c$，因为它可以去最近的充电站再往终点走。那么我们要求的就是将每条边的代价算出来，然后从a到b就是这个路径上的边权的最大值。那么我们要使最大值最小，就用kruskal就行了。
之后我们建出最小生成树之后将边权存到儿子的点权上，然后查询的话就查a~b的路径上的最大值即可。注意lca的点权不能算进去。
代码非常长，好像还有别的做法更容易点。时间复杂度一般。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
const ll inf=1e18;
struct edge{int to,next;ll w;
}e[N*2];
int cnt,head[N];
void add(int x,int y,ll w){e[cnt].to=y;e[cnt].w=w;e[cnt].next=head[x];head[x]=cnt++;
}
struct node{int id;ll w;bool operator< (const node& a)const {return w>a.w;}
};
struct Kruskal{int x,y;ll w;bool operator< (const Kruskal& a)const {return w<a.w;}
}edg[N];
priority_queue<node>Q;
ll dis[N],mx[N*4];
void dij(){while(!Q.empty()){node u=Q.top();Q.pop();if(u.w!=dis[u.id])continue;for(int i=head[u.id];~i;i=e[i].next){int ne=e[i].to;if(dis[ne]>dis[u.id]+e[i].w){dis[ne]=dis[u.id]+e[i].w;Q.push({ne,dis[ne]});}}}
}
int fa[N];
int finds(int x){return x==fa[x]?fa[x]:fa[x]=finds(fa[x]);}
int f[N][25],dep[N],siz[N],son[N],tim,pos[N],top[N];
int n,m,k,q;
void dfs1(int u)
{siz[u]=1;for (int i=head[u];~i;i=e[i].next){int v=e[i].to;if (v!=f[u][0]){f[v][0]=u;dep[v]=dep[u]+1;dfs1(v);siz[u]+=siz[v];if (son[u]==0||siz[v]>siz[son[u]])son[u]=v;}}
}
void dfs2(int u,int ff)
{tim++;top[u]=ff;pos[u]=tim;if (son[u]) dfs2(son[u],ff);for (int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v!=f[u][0]&&v!=son[u])dfs2(v,v);}
}void deal(){for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];return f[x][0];
}void add(int l,int r,int root,int p,ll val)
{if(l==r){mx[root]=val;return ;}int mid=l+r>>1;if(mid>=p)add(l,mid,root<<1,p,val);elseadd(mid+1,r,root<<1|1,p,val);mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
ll ask(int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr)return mx[root];int mid=l+r>>1;ll ans=0;if(mid>=ql)ans=ask(l,mid,root<<1,ql,qr);if(mid<qr)ans=max(ask(mid+1,r,root<<1|1,ql,qr),ans);return ans;
}
ll query(int x,int y)
{ll ans=0;while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);ans=max(ans,ask(1,n,1,pos[top[x]],pos[x]));x=f[top[x]][0];}if (pos[x]>pos[y]) swap(x,y);ans=max(ans,ask(1,n,1,pos[x],pos[y]));return ans;
}
int in[N];
int main()
{memset(head,-1,sizeof(head));scanf("%d%d%d%d",&n,&m,&k,&q);int x,y;ll w;for(int i=1;i<=m;i++)scanf("%d%d%lld",&edg[i].x,&edg[i].y,&edg[i].w),add(edg[i].x,edg[i].y,edg[i].w),add(edg[i].y,edg[i].x,edg[i].w);for(int i=1;i<=n;i++)dis[i]=inf,fa[i]=i;for(int i=1;i<=k;i++)Q.push({i,0}),dis[i]=0;dij();for(int i=1;i<=m;i++)edg[i].w+=dis[edg[i].x]+dis[edg[i].y];sort(edg+1,edg+1+m);cnt=0;memset(head,-1,sizeof(head));for(int i=1;i<=m;i++){int fax=finds(edg[i].x),fay=finds(edg[i].y);if(fax==fay)continue;add(edg[i].x,edg[i].y,edg[i].w),add(edg[i].y,edg[i].x,edg[i].w);fa[fay]=fax;in[i]=1;}dep[1]=1;dfs1(1);dfs2(1,1);deal();for(int i=1;i<=m;i++){if(!in[i])continue;x=edg[i].x,y=edg[i].y;if(dep[x]>dep[y])add(1,n,1,pos[x],edg[i].w);elseadd(1,n,1,pos[y],edg[i].w);}while(q--){int x,y;scanf("%d%d",&x,&y);int l=lca(x,y),firstson;ll ans=0;if(y!=l){firstson=y;for(int i=20;i>=0;i--)if(dep[f[firstson][i]]>dep[l])firstson=f[firstson][i];ans=query(firstson,y);}if(x!=l){firstson=x;for(int i=20;i>=0;i--)if(dep[f[firstson][i]]>dep[l])firstson=f[firstson][i];ans=max(ans,query(firstson,x));}printf("%lld\n",ans);}return 0;
}

这篇关于Codeforces 1253 F. Cheap Robot —— 想法，dijkstra+kruskal重构树+并查集+树链剖分+lca，有丶东西的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---