cf545 E. Paths and Trees

本文主要是介绍cf545 E. Paths and Trees，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

给定正边权无向图和起点，求边权和最小的最短路径树

思路：

想象跑一遍 dijkstra 后，对于某边 \(u\to v\) 若 \(d_v \neq d_u+w\)（\(w\) 表示该边的边权），那么这条边不可能在最短路径树上，把它删除

然后用剩下的边做一棵最小生成树就是答案，即每次选择最小的边连接两个连通块。

怎么实现呢？自然可以照着上述说法写一遍，但有更帅的写法

法一：上述方法等价于，在跑 dijkstra 的过程中找到 \(v\) 的最短路中最后一条边的边权最小的那条。即记录到每个点的最短路的最后一条边，当 \(d_v>d_u+w\) 或者 \(d_v=d_u+w\) 且 \(w<last_v\) 时都更新

法二（妙）：实际上只需要把 dijkstra 中 if 里面的符号改成大于等于就可以了！这是因为根据 dijkstra 的性质，出队的点的 \(d\) 值是递增的，所以找到的最后一条最短路上的最后一条边就是最小的！

const signed N = 3 + 3e5;
int n, m, rt; vector<array<ll,3>> G[N]; //v,w,id

int ID[N], W[N]; //最短路径的最后一条边的信息
void sol() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        G[x].pb({y,z,i}), G[y].pb({x,z,i});
    }
    cin >> rt;

    priority_queue<PLL> q; q.push({0,rt});
    vector<bool> vis(n+1,0); vector<ll> d(n+1,LLINF); d[rt] = 0;
    while(q.size()) {
        int u = q.top().se; q.pop();
        if(vis[u]) continue; vis[u] = true;
        for(auto &[v,w,id]: G[u]) if(d[v] >= d[u] + w) //只需要改成>=
            d[v] = d[u] + w, ID[v] = id, W[v] = w, q.push({-d[v],v});
    }

    cout << accumulate(W + 1, W + 1 + n, 0ll) << endl;
    for(int i = 1; i <= n; i++) if(ID[i]) cout << ID[i] << ' ';
}

这篇关于cf545 E. Paths and Trees的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！