Codeforces 1253 F - Cheap Robot (최 단 길 + 검색 집합 / Kruskal 트 리)

제목 의 대의
n 시 m 변 무방 향도, k 개 관건, q 개 질문 (a, b).a 부터 b 까지 필요 한 최소 용량 c 가 얼마 인지 물 어보 세 요.보증 a, b 가 관건 이다.당신 의 에너지 탱크 는 최대 c 에너지 가 있 습 니 다. 걸 을 때마다 변 권 의 그렇게 많은 에 너 지 를 소모 합 니 다.중요 한 점 에서 에 너 지 를 채 울 수 있다.매번 물 어 볼 때마다 필요 한 최소한 의 에너지.k , n ≤ 1 e 5 , q , m ≤ 3 e 5 k,n\le1e5,q,m\le 3e5 k,n≤1e5,q,m≤3e5
문제 풀이 의 사고 방향.
모든 관건 점 을 소스 로 하여 다 원 최 단 로 를 한 번 구하 고 한 점 u u 에 대해 현재 에너지 x < d i s [u] x < dis [u] x < dis [u] x < dis [u] 가 도착 하지 못 할 것 이다. 만약 x > = d i s [u] x > = dis [u] x > = dis [u] 라면 x x x x 는 ≤ c - d i s [u] \ l c - dis [u] ≤ c - dis [u] 의 것 이다.또 x > = d i s [u] x > = dis [u] x > = dis [u] 로 인해 가장 가 까 운 관건 으로 달 려 가 다시 돌아 올 수 있 기 때문에 x 각 점 u 의 에 너 지 는 c - d i s [u] c - dis [u] c - dis [u] 로 유지 할 수 있다.u − > v u - > v u − > v 가 걸 을 수 있 으 려 면 c − d i s [u] − w > = d i s [v] c - dis [u] - w > = dis [v] c − dis [u] - w > = dis [v] 로 전환 하여 d i s [u] + d i s [v] + w ≤ c dis [u] + dis [v] + w \ l c dis [u] + dis [v] + w ≤ c.d i s [u] + d i s [v] + w dis [u] + dis [v] + w dis [u] + dis [v] + w 를 새로운 변 권 으로 새 그림 을 만 듭 니 다.문 제 는 한 점 에서 다른 점 까지 지나 가 는 경로 의 최대 치 를 최소 화 하 는 것 이다.두 가지 방법: 1. 오프라인 방법 은 가중치 에 따라 정렬 한 다음 에 집합 합 니 다.문의 가 점 에 걸 려 있다.처리 해 야 할 문의 수량 에 따라 시작 식 통합 을 진행 합 니 다. 질문 당 최대 l o g log 회 이동 2. 온라인 방법 으로 Kruskal 트 리 를 만 든 후 트 리 에 lca 의 점 권 을 배가 합 니 다.
오프라인 방법:

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define P pair
using namespace std;
const int maxn = 3e5 + 50;
struct edge{
     
    int u ,v , nxt;
    ll w;
    bool operator < (const edge &a)const{
     return w < a.w;}
}e[maxn*2];
int cnt = 0;
int head[maxn];
void add(int u, int v, ll w){
     
    e[cnt] = (edge){
     u, v, head[u], w};
    head[u] = cnt++;
}
int n, m, k, Q;
priority_queue<P, vector<P>, greater<P> > q;
ll dis[maxn];
void dij(){
     
    while(q.size()){
     
        P temp = q.top();q.pop();
        int u = temp.second;
        if(dis[u] < temp.first) continue;
        for(int i = head[u]; ~i; i = e[i].nxt){
     
            int v = e[i].v; ll w = e[i].w;
            if(dis[v] > dis[u] + w){
     
                dis[v] = dis[u] + w;
                q.push(P(dis[v], v));
            }
        }
    }
}
void init(){
     
    memset(head, -1, sizeof head);
    cin>>n>>m>>k>>Q;
    for(int i = 0; i < m; ++i){
     
        int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= k; ++i){
     
        dis[i] = 0; q.push(P(0, i));
    }dij();
    int tp = 0;
    for(int i = 0; i < cnt; i += 2){
     
        e[tp] = e[i];
        e[tp++].w += dis[e[i].u]+dis[e[i].v];
    }
    cnt = tp;
}
ll ans[maxn*5];
struct node{
     int v, id;};
vector<node> g[maxn];
int fa[maxn];
int fnd(int x){
     
    if(x == fa[x]) return x;
    return fa[x] = fnd(fa[x]);
}
void link(int u, int v, ll w){
     
    u = fnd(u); v = fnd(v);
    if(u == v) return;
    if(g[u].size() > g[v].size()) swap(u, v);
    for(int i = 0; i < g[u].size(); ++i){
     
        int x = g[u][i].v;
        int id = g[u][i].id;
        if(fnd(x) == v)
            ans[id] = w;
        else
            g[v].push_back(g[u][i]);
    }
    fa[u] = v;
    g[u].clear();//g[u].shrink_to_fit(); return;
}
void sol(){
     
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 0; i < Q; ++i){
     
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back((node){
     v, i});
        g[v].push_back((node){
     u, i});
    }
    sort(e, e+cnt);
    for(int i = 0; i < cnt; ++i) link(e[i].u, e[i].v, e[i].w);
    for(int i = 0; i < Q; ++i) {
     
        printf("%lld
", ans[i]);
    }
}
int main()
{
     
    init();
    sol();
}

온라인 방법:

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define P pair
using namespace std;
const int maxn = 3e5 + 50;
struct edge{
     
    int u ,v , nxt;
    ll w;
    bool operator < (const edge &a)const{
     return w < a.w;}
}e[maxn*2];
int cnt = 0;
int head[maxn];
void add(int u, int v, ll w){
     
    e[cnt] = (edge){
     u, v, head[u], w};
    head[u] = cnt++;
}
int n, m, k, Q;
priority_queue<P, vector<P>, greater<P> > q;
ll dis[maxn];
void dij(){
     
    while(q.size()){
     
        P temp = q.top();q.pop();
        int u = temp.second;
        if(dis[u] < temp.first) continue;
        for(int i = head[u]; ~i; i = e[i].nxt){
     
            int v = e[i].v; ll w = e[i].w;
            if(dis[v] > dis[u] + w){
     
                dis[v] = dis[u] + w;
                q.push(P(dis[v], v));
            }
        }
    }
}
void init(){
     
    memset(head, -1, sizeof head);
    cin>>n>>m>>k>>Q;
    for(int i = 0; i < m; ++i){
     
        int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= k; ++i){
     
        dis[i] = 0; q.push(P(0, i));
    }dij();
    int tp = 0;
    for(int i = 0; i < cnt; i += 2){
     
        e[tp] = e[i];
        e[tp++].w += dis[e[i].u]+dis[e[i].v];
    }
    cnt = tp;
}
ll ans[maxn];
int fa[maxn*2];
int fnd(int x){
     
    if(x == fa[x]) return x;
    return fa[x] = fnd(fa[x]);
}
int tot;
vector<int> g[maxn];
ll val[maxn];
int f[maxn][20], dep[maxn];
void get_mst(){
     
    tot = n;
    for(int i = 0; i <cnt; ++i){
     
        int u = e[i].u; int v = e[i].v;
        u = fnd(u); v = fnd(v); if(u == v) continue;
        fa[u] = fa[v] = ++tot; fa[tot] = tot; val[tot] = e[i].w;
        g[tot].push_back(v); f[v][0] = tot;
        g[tot].push_back(u); f[u][0] = tot;
    }
}
void dfs(int u){
     
    for(int i = 0; i+1 < 20; ++i) f[u][i+1] = f[f[u][i]][i];
    for(int i = 0; i < g[u].size(); ++i) dep[g[u][i]] =dep[u]+1, dfs(g[u][i]);
}
int lca(int u, int v){
     
    if(dep[u] > dep[v]) swap(u, v);
    int d = dep[v] - dep[u]; for(int i = 19; i >= 0; --i) if(d>>i&1) v = f[v][i];
    if(u == v) return u;
    for(int i = 19; i >= 0; --i){
     
        if(f[u][i] == f[v][i]) continue;
        u = f[u][i]; v = f[v][i];
    }return f[u][0];
}
void sol(){
     
    for(int i = 1; i <= n; ++i) fa[i] = i;
    sort(e, e+cnt);
    get_mst();
    dfs(tot);
    while(Q--){
     
        int u, v; scanf("%d%d", &u, &v);
        printf("%lld
", val[lca(u,v)]);
    }
}
int main()
{
     
    init();
    sol();
}