Cheap Robot

XichenOC · 2024-11-12 20:42:18 · 题解

Cheap Robot

题目翻译：

给一个带N个点的带权无向连通图，并给定k每经过一个边就要消耗边的边权w，而当到达1 \sim k的节点处可以将点充满。求从a到b所需要的最小点容量c。及一次性消耗的电量不能超过c。

前置知识：

1.最近公共祖先LCA

2.最小生成树kruskal

3.并查集

4.最短路dijkstra

思路：

普通解法：

我们读完题肯定可以想到，用全源最短路求1 \sim k的最短路，再求每个节点所邻的最近的充电节点，求出里面耗电的最大值最小即可，但这样复杂度就到了n^2logn，肯定会超

正解：

1.我们在仔细思考会发现，我们要尽量把机器人移到充电站，在在充电站之间移动一般是最优的，因此我们可以预处理出每个节点离充电站的最小距离dis_i。那如何求了。我们可以先建一个超级原点0号点，它与所有充电站，即1 \sim k有一条边权为零的边，则由这个点到任意节点的最短路就是这个节点到最近充电站的距离。原因是，任意非充电站节点到超级原点必经过充电站，而充电站到超级原点的边权为零，则该点到超级原点的最短路等于到充电站的最短路。因此只需跑一遍dijkstra求出dis_i即可。

建边

for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    e[u].push_back({v,w});
    e[v].push_back({u,w});
}
for(int i=1;i<=k;i++){
    e[0].push_back({i,0});
}

dijkstra

int dis[N],vis[N];
vector<edge>e[N];
priority_queue<node>q;
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    q.push({0,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}

2.又由已知条件，c，当前剩余电量k，和点离充电站的最短路dis_i可得出关系

c \geq x \geq dis_i

而从充电站走到点至少消耗了dis_i则不等式可以改为

c-dis_i \geq x \geq dis_i

令下一个点为j边权为w_{i,j},同理有

c-dis_j \geq x-w_{i,j} \geq dis_j

将两个式子合并即可得到

dis_j \le c-dis_i-w_{i,j}

简单转换可知

c \geq dis_i+dis_j+w_{i,j}

则由此可知从i到j的最小消耗电量为dis_i+dis_j+w_{i,j}。

3.既然已经求出两点之间的最小消耗电量，而题目又是多次询问，求最大电容量及从a到b的每条路的最大耗电量的最小值，因此我们可以先将任意两点之间的边权换成dis_i+dis_j+w_{i,j}，在跑一遍kruskal求出最小生成树。在求任意两点路径上边权的最大值即可

建新图

for(int u=1;u<=n;u++){
    for(auto ed:e[u]){
        now.push_back({u,ed.v,ed.w+dis[u]+dis[ed.v]});
    }
}

kruskal

int fa[N];
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
void kruskal(){
    sort(now.begin(),now.end(),cmp);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    int cnt=0;
    for(auto ed:now){
        if(find(ed.u)!=find(ed.v)){
            cnt++;
            tr[ed.u].push_back({ed.v,ed.w});
            tr[ed.v].push_back({ed.u,ed.w});
            fa[find(ed.u)]=find(ed.v);
            if(cnt==n-1)break;
        }
    }
}

4.要求树上的路径问题，我们可以简单想到求LCA，于是直接用倍增求LCA，只需要将求和改为求max即可

LCA

int f[N][22];
int deep[N],maxm[N][22];
void init(){
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
            maxm[j][i]=max(maxm[j][i-1],maxm[f[j][i-1]][i-1]);
        }
    }
}
void dfs(int p,int father){
    f[p][0]=father;
    for(auto ed:tr[p]){
        int v=ed.v,w=ed.w;
        if(v==father)continue;
        maxm[v][0]=w;
        deep[v]=deep[p]+1;
        dfs(v,p);
    }
}
int lca(int x,int y){
    int ans=0;
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(deep[f[x][i]]<deep[y]) continue;
        ans=max(ans,maxm[x][i]);
        x=f[x][i];
    }
    if(x==y) return ans;
    for(int i=20;i>=0;i--){
        if(f[x][i]==f[y][i])continue;
        ans=max(ans,max(maxm[x][i],maxm[y][i]));
        x=f[x][i];
        y=f[y][i];
    }
    ans=max(ans,max(maxm[x][0],maxm[y][0]));
    return ans;
}

完整流程：

$2.$跑一遍以超级原点为起点的$dijkstra$，求出$dis_i $4.$跑一遍新图$kruskal$求出最小生成树 $5.$在最小生成树上求$LCA$，维护路径中边权的最大值，并输出结果 # 完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct edge{
    int v,w;
}; 
struct node{
    int u,dis;
    bool operator<(const node &a)const{return dis>a.dis;}
};
struct E{
    int u,v,w;
};
bool cmp(E x,E y){
    return x.w<y.w;
}
vector<E>now;
vector<edge>tr[N];
int n,m;
int dis[N],vis[N];
vector<edge>e[N];
priority_queue<node>q;
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    q.push({0,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}
int fa[N];
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
int f[N][22];
int deep[N],maxm[N][22];
void init(){
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
            maxm[j][i]=max(maxm[j][i-1],maxm[f[j][i-1]][i-1]);
        }
    }
}
void dfs(int p,int father){
    f[p][0]=father;
    for(auto ed:tr[p]){
        int v=ed.v,w=ed.w;
        if(v==father)continue;
        maxm[v][0]=w;
        deep[v]=deep[p]+1;
        dfs(v,p);
    }
}
int lca(int x,int y){
    int ans=0;
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(deep[f[x][i]]<deep[y]) continue;
        ans=max(ans,maxm[x][i]);
        x=f[x][i];
    }
    if(x==y) return ans;
    for(int i=20;i>=0;i--){
        if(f[x][i]==f[y][i])continue;
        ans=max(ans,max(maxm[x][i],maxm[y][i]));
        x=f[x][i];
        y=f[y][i];
    }
    ans=max(ans,max(maxm[x][0],maxm[y][0]));
    return ans;
}
void kruskal(){
    sort(now.begin(),now.end(),cmp);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    int cnt=0;
    for(auto ed:now){
        if(find(ed.u)!=find(ed.v)){
            cnt++;
            tr[ed.u].push_back({ed.v,ed.w});
            tr[ed.v].push_back({ed.u,ed.w});
            fa[find(ed.u)]=find(ed.v);
            if(cnt==n-1)break;
        }
    }
}
signed main(){
    int k,q;
    cin>>n>>m>>k>>q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    for(int i=1;i<=k;i++){
        e[0].push_back({i,0});
    }
    dijkstra();
    for(int u=1;u<=n;u++){
        for(auto ed:e[u]){
            now.push_back({u,ed.v,ed.w+dis[u]+dis[ed.v]});
        }
    }
    kruskal();
    deep[1]=1;
    dfs(1,-1);
    init();

    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
}