专栏文章

题解：P14545 [IO 2024 #3] 安全航行

llzx111218
P14545题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4iofh
此快照首次捕获于
2025/12/01 20:26
3 个月前
此快照最后确认于
2025/12/01 20:26
3 个月前
查看原文

P14545 [IO 2024 #3] 安全航行

题目传送门

思路

好题，建议紫。
给定一个连通无向图，包含 nn 个点和 mm 条边，每条边有一个强度权值 wiw_i。对于每条边 ff，求最大的强度值 pfp_f，使得将 ff 的强度改为 pfp_f 后，存在一个包含 ff 的最小生成树。
由于是稀疏图，考虑 Kruskal。
我们可以分树边和非树边算答案：
  • 非树边答案：
    • 根据 Kruskal 的性质，非树边 e(u,v)e(u,v) 加入 MST 会形成一个环。若 ee 能出现在某个 MST 中，其权值 pep_e 必须不大于环上原 MST 路径的最大边权。
    • 因此：非树边的答案 = 其两端点在原 MST 中路径的最大边权。
  • 树边答案：
    • 树边 ee 被删除后，原 MST 会被分割为两个连通块 AA 和 BB。所有连接 AA 和 BB 的非树边中，权值最小的那个值就是 pep_e 的最大值。若没有这样的非树边，pep_e 就是题目限制的最大值 10910^9。
    • 因此：树边的答案 = 所有跨越其分割块的非树边的最小权值（若没有则为 10910^9）。
树链预处理用两次非递归 DFS 解决即可，比较简单：
  1. 计算每个节点的子树大小、重儿子。
  2. 计算每个节点的链顶、位置编号。
时间复杂度为 O(mlog⁡m+nlog⁡n+mlog⁡2n)\mathcal{O}(m \log m+n \log n+m \log^2n)。
空间复杂度为 O(n+m)\mathcal{O}(n+m)。
CodeCPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int INF = 1e18, N = 1e5 + 78, M = 4e5 + 78, MAN = 2 << 20;
int n, m, ans[M], dp[N], arr[20][N], maxx[20][N], top[N], sz[N], son[N], pos[N], tree[MAN], lazy[MAN], num, idx;
namespace fastIO{char *p1,*p2,buf[N];
	#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
	inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
	inline void read(string&s){char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
	inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
	inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
	inline void write(const string&s){for(int i=0;i<(int)s.size();i++){putchar(s[i]);}}
	inline void write(const char&c){putchar(c);}
}using namespace fastIO;
struct Edge{
    int u, v, id, w;
    bool f;
    Edge(){}
    Edge(int u_, int v_, int w_, int id_) : u(u_), v(v_), id(id_), w(w_), f(false){}
    bool operator<(Edge& other){
        return w < other.w;
    }
}edges[M];
struct DSU{
    int a[N], b[N];
    void init(int n){
        for (int i = 1; i <= n; i++) a[i] = i, b[i] = 1;
    }
    int find(int x){
        while(a[x] != x) a[x] = a[a[x]], x = a[x];
        return x;
    }
    bool merge(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return false;
        if(b[x] < b[y]) swap(x, y);
        a[y] = x, b[x] += b[y];
        return true;
    }
}dsu;
vector<pair<int, int>> adj[N];
void dfs1(int rt){
    stack<tuple<int, int, int, bool>> st;
    st.emplace(rt, 0, 0, false);
    while(!st.empty()){
        auto t = st.top(); st.pop();
        int u = get<0>(t), f = get<1>(t), w = get<2>(t); bool vis = get<3>(t);
        if(vis){
            for(int i = 1; i < 20; i++){
                arr[i][u] = arr[i-1][arr[i-1][u]];
                maxx[i][u] = max(maxx[i-1][u], maxx[i-1][arr[i-1][u]]);
            }
            for(auto& p : adj[u]){
                int v = p.first; int nw = p.second;
                if (v != f) st.emplace(v, u, nw, false);
            }
        }else{
            arr[0][u] = f;
            dp[u] = dp[f] + 1;
            maxx[0][u] = w;
            st.emplace(u, f, w, true);
        }
    }
}
int query(int u, int v){
    int res = 0;
    if(dp[u] < dp[v]) swap(u, v);
    for(int i = 20-1; i >= 0; i--){
        if(dp[arr[i][u]] >= dp[v]){
            res = max(res, maxx[i][u]);
            u = arr[i][u];
        }
    }
    if(u == v) return res;
    for(int i = 20-1; i >= 0; i--){
        if(arr[i][u] != arr[i][v]){
            res = max(res, maxx[i][u]);
            res = max(res, maxx[i][v]);
            u = arr[i][u], v = arr[i][v];
        }
    }
    res = max(res, maxx[0][u]);
    res = max(res, maxx[0][v]);
    return res;
}
void build(int n){
    num = 1;
    while(num < n) num <<= 1;
    for(int i = 0; i < 2 * num; i++){
        tree[i] = INF;
        lazy[i] = INF;
    }
}
void pushdown(int rt){
    if(lazy[rt] != INF && rt < num){
        int lc = rt << 1, rc = rt << 1 | 1;
        tree[lc] = min(tree[lc], lazy[rt]);
        lazy[lc] = min(lazy[lc], lazy[rt]);
        tree[rc] = min(tree[rc], lazy[rt]);
        lazy[rc] = min(lazy[rc], lazy[rt]);
        lazy[rt] = INF;
    }
}
void update(int L, int R, int w){
    L += num - 1;
    R += num - 1;
    int l = L, r = R;
    while(l <= r){
        if(l & 1) pushdown(l), tree[l] = min(tree[l], w), lazy[l] = min(lazy[l], w), l++;
        if(!(r & 1)) pushdown(r), tree[r] = min(tree[r], w), lazy[r] = min(lazy[r], w), r--;
        l >>= 1, r >>= 1;
    }
}
int queryy(int p){
    p += num - 1;
    int res = tree[p];
    for(int i = p >> 1; i >= 1; i >>= 1){
        res = min(res, tree[i]);
    }
    return res;
}
void dfs2(int rt){
    stack<tuple<int, int, bool> > st;
    st.emplace(rt, 0, false);
    while(!st.empty()){
        auto t = st.top(); st.pop();
        int u = get<0>(t), f = get<1>(t);
        bool vis = get<2>(t);
        if(vis){
            sz[u] = 1, son[u] = 0;
            for(auto& p : adj[u]){
                int v = p.first;
                if(v == f) continue;
                sz[u] += sz[v];
                if(sz[v] > sz[son[u]]) son[u] = v;
            }
        }else{
            st.emplace(u, f, true);
            for(auto it = adj[u].rbegin(); it != adj[u].rend(); it++){
                int v = it->first;
                if(v != f) st.emplace(v, u, false);
            }
        }
    }
}
void dfs3(int rt){
    stack<tuple<int, int, bool> > st;
    st.emplace(rt, rt, false);
    idx = 0;
    while(!st.empty()){
        auto t = st.top(); st.pop();
        int u = get<0>(t), tp = get<1>(t);
        bool vis = get<2>(t);
        if(vis){
            for(auto it = adj[u].rbegin(); it != adj[u].rend(); it++){
                int v = it->first;
                if(v != arr[0][u] && v != son[u]) st.emplace(v, v, false);
            }
            if(son[u]) st.emplace(son[u], tp, false);
        }else{
            top[u] = tp;
            pos[u] = ++idx;
            st.emplace(u, tp, true);
        }
    }
}
void updatee(int u, int v, int w){
    while(top[u] != top[v]){
        if(dp[top[u]] < dp[top[v]]) swap(u, v);
        update(pos[top[u]], pos[u], w);
        u = arr[0][top[u]];
    }
    if(dp[u] > dp[v]) swap(u, v);
    if(u != v) update(pos[u] + 1, pos[v], w);
}
signed main(){
    read(n), read(m);
    for(int i = 0; i < m; i++){
        int u, v, w;
        read(u), read(v), read(w); 
        edges[i] = Edge(u, v, w, i);
    }
    sort(edges, edges + m);
    dsu.init(n);
    for(int i = 0; i < m; i++){
        Edge& e = edges[i];
        if(dsu.merge(e.u, e.v)){
            e.f= true;
            adj[e.u].emplace_back(e.v, e.w);
            adj[e.v].emplace_back(e.u, e.w);
        }
    }
    dp[0] = 0;
    dfs1(1), dfs2(1), dfs3(1), build(n);
    for(int i = 0; i < m; i++){
        Edge& e = edges[i];
        if(!e.f){
            int mx = query(e.u, e.v);
            ans[e.id] = mx;
            updatee(e.u, e.v, e.w);
        }
    }
    for(int i = 0; i < m; i++){
        Edge& e = edges[i];
        if(e.f){
            int u = e.u, v = e.v;
            if(arr[0][v] == u) swap(u, v);
            int temp = queryy(pos[u]);
            ans[e.id] = (temp == INF) ? 1e9 : temp;
        }
    }
    for(int i = 0; i < m; i++){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...