最开始啃这题的时候我还是个不会$lca$的人，看代码看的没有一点头绪，现在趁着寒假补了很多关于图论的知识点，回头在看这题还是有很多值得学习的地方。

Solution 1 (offline):

原题解：

Sort edges by new weight. Add them progressively, maintaining connexity with DSU.

As soon as two endpoints of a query become connected, we should put current capacity (i.e. new weight of the last edge added) as answer for this query.

To effeciently detect this, we can put tokens on endpoints of each query, and each time we do union (of DSU), we make tokens go up to the parent. If we do union by rank, each token will move at most$O(logn)$times.

离线的做法，我看了好久，开始的时候不太理解，后来看某$OI$选手的启发式合并的博客，我才有点感觉了。

先把新边按权值排序，然后逐步加边，将端点进行启发式合并（实际上就是最小生成树，考虑MST中每条边对答案的贡献）

比如我先加入一条1->3的边，那么我就去找和1相关的查询又没有在3所在的集合中

如果有就记录答案，因为有的话说明查询的两点间路径经过1->3这条边，又由于树中两点路径唯一，边是从小到大加进来的，一旦联通当前边的权值就是答案

至于为什么不去找和3相关的查询有没有在1所在的集合中，是因为预处理查询的时候加入的点对是双向的（可以自己脑补下，不太好描述）

没有的话就合并查询，由于边的加入使得这两个点联通，那么对应的查询也应该合并。

那么该如何合并呢？当然是启发式合并，其实就是小的集合并到大的集合里面。其实怎么合并都可以，答案都是对的，但是会出现这种情况：

原因是合并采取的方式是vector数组push_back()，假如你每次都是把大集合push_back()到小集合里面，那么内存可能会爆掉

看下代码应该就知道了：

#include <bits/stdc++.h>

#define pb push_back

#define ll long long

#define fi first

#define se second

#define inf 1e15

using namespace std;

const int maxn = 3e6+10;

int n, m, k, q;

int f[maxn], head[maxn], cnt;

ll dis[maxn], ans[maxn];

priority_queue<pair<ll, int>> que;

bool vis[maxn];

vector<pair<int,int>> tmp[maxn];

struct node1{

    int to, next;

    ll w;

}e[maxn<<1];

struct node2{

    int u, v;

    ll w;

    bool operator < (const node2 &x) const{

        return w<x.w;

    }

}edge[maxn];

//不能进行路径压缩, 那样会破坏原有的信息

int find(int x){

    return f[x]==x ? x : find(f[x]);

}

void add(int u, int v, ll w){

    e[++cnt].to = v;

    e[cnt].w = w;

    e[cnt].next = head[u];

    head[u] = cnt;

}

void dijkstra(){

    for(int i = 1; i <= k; i++)

        dis[i] = 0, que.push({0, i});

    for(int i = k+1; i <= n; i++) dis[i] = inf;

    while(!que.empty()){

        int u = que.top().second; que.pop();

        if(vis[u]) continue; vis[u] = 1;

        for(int i = head[u]; i; i = e[i].next)

            if(dis[u]+e[i].w<dis[e[i].to]){

                dis[e[i].to] = dis[u] + e[i].w;

                que.push({-dis[e[i].to], e[i].to}); //默认优先级较大, 所以需要*(-1)

            }

    }

}

int main(){

    scanf("%d%d%d%d", &n, &m, &k, &q);

    for(int i = 1; i <= m; i++){

        int u, v;

        ll w;

        scanf("%d%d%lld", &u, &v, &w);

        add(u, v, w), add(v, u, w);

        edge[i] = node2{u, v, w};

    }

    dijkstra();

    for(int i = 1; i <= m; i++) edge[i].w += dis[edge[i].u]+dis[edge[i].v];

    sort(edge+1, edge+1+m);

    for(int i = 1; i <= q; i++){

        int u, v;

        scanf("%d%d", &u, &v);

        tmp[u].pb({v, i}), tmp[v].pb({u, i});

    }

    for(int i = 1; i <= n; i++) f[i] = i;

    for(int i = 1; i <= m; i++){

        int t1 = find(edge[i].u), t2 = find(edge[i].v);

        if(t1==t2) continue;

        if(tmp[t1].size()>tmp[t2].size()) swap(t1, t2);

        for(auto it:tmp[t1]){

            //if(ans[it.fi]) continue;

            if(find(it.fi)==t2) ans[it.se] = edge[i].w;

            else tmp[t2].pb(it); //合并查询

        }

        f[t1] = t2;

    }

    for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);

}

Solution 2 (online):

在线做法这就比较直接，直接用倍增$lca$ / $Kurskal$生成树+$lca$求最小瓶颈路就行了，思路很清晰

正好也学了树链剖分，可以写写练下手

#include <bits/stdc++.h>

#define ll long long

#define inf 1e15

using namespace std;

const int maxn = 6e5+10;

int n, m, k, q, u, v, cost, t1, t2;

int head1[maxn], head2[maxn];

int f[maxn], dep[maxn], son[maxn], size[maxn], top[maxn];

ll w[maxn], dis[maxn];

priority_queue<pair<ll, int>> que;

bool vis[maxn];

struct edge{

    int to, next;

    ll w;

}e1[maxn<<1], e2[maxn];

struct node{

    int u, v;

    ll w;

    bool operator < (const node &x) const{

        return w < x.w;

    }

}data[maxn];

//路径压缩

int find(int x){

    return f[x]==x ? x: f[x]=find(f[x]);

}

void dijkstra(){

    for(int i = 1; i <= k; i++)

        dis[i] =  0, que.push({0, i});

    for(int i = k+1; i <= n; i++) dis[i] = inf;

    while(!que.empty()){

        int u = que.top().second; que.pop();

        if(vis[u]) continue; vis[u] = 1;

        for(int i = head1[u]; i; i = e1[i].next)

            if(dis[u]+e1[i].w<dis[e1[i].to]){

                dis[e1[i].to] = dis[u] + e1[i].w;

                que.push({-dis[e1[i].to], e1[i].to});

            }

    }

}

void add1(int u, int v, int w){

    e1[++t1].next = head1[u];

    e1[t1].to = v, e1[t1].w = w;

    head1[u] = t1;

}

void add2(int u, int v){

    e2[++t2].next = head2[u];

    e2[t2].to = v;

    head2[u] = t2;

}

void dfs1(int u, int fa){

    size[u] = 1;

    for(int i = head2[u]; i; i = e2[i].next){

        int v = e2[i].to;

        if(v==fa) continue;

        dep[v] = dep[u] + 1, f[v] = u;

        dfs1(v, u), size[u] += size[v];

        if(size[v]>size[son[u]]) son[u] = v;

    }

}

void dfs2(int u, int topf){

    top[u] = topf;

    if(son[u]) dfs2(son[u], topf);

    for(int i = head2[u]; i; i = e2[i].next){

        int v = e2[i].to;

        if(v==son[u]||v==f[u]) continue;

        dfs2(v, v);

    }

}

int lca(int u, int v){

    while(top[u]!=top[v]){

        if(dep[top[u]]<dep[top[v]]) swap(u, v);

        u = f[top[u]];

    }

    return dep[u]<dep[v] ? u : v;

}

int main(){

    scanf("%d%d%d%d", &n, &m, &k, &q);

    for(int i = 1; i <= m; i++){

        scanf("%d%d%d", &u, &v, &cost);

        add1(u, v, cost), add1(v, u, cost);

        data[i] = node{u, v, cost};

    }

    dijkstra();

    for(int i = 1; i <= m; i++) data[i].w += dis[data[i].u]+dis[data[i].v];

    sort(data+1, data+1+m);

    for(int i = 1; i <= n; i++) f[i] = i;

    int cnt = n;

    for(int i = 1; i <= m; i++){

        int fu = find(data[i].u), fv = find(data[i].v);

        if(fu==fv) continue;

        w[++cnt] = data[i].w;

        f[cnt] = f[fu] = f[fv] = cnt;

        add2(cnt, fu), add2(cnt, fv);

    }

    dfs1(cnt, 0), dfs2(cnt, cnt);

    while(q--){

        scanf("%d%d", &u, &v);

        printf("%lld\n", w[lca(u, v)]);

    }

}

最新文章

  1. CSS3线性渐变和径向渐变
  2. 发布新博客皮肤red_autumnal_leaves
  3. IntelliJ IDEA使用（3）——IDEA连接Git
  4. Python：time模块&amp;序列化&amp;生成随机数&amp;反射
  5. HTML5本地存储之localStorage、sessionStorage
  6. HDU 5688 Problem D map
  7. 附录三 嵌入式C程序的编译与调试
  8. SwiftyJSON 中文介绍
  9. adobe 蛋疼的套装， 想安装一个Flash Professional CS6，标准版还没有...
  10. JAVA bean与XML互转的利器---XStream
  11. padding and margin.
  12. c语言小练习（蛮好玩的）
  13. linux之getcwd函数解析
  14. Windbg抓取程序崩溃的dmp文件的方法
  15. 关于python编译的一点小结
  16. asp.net mvc 4 项目升级到 asp.net mvc5
  17. UEFI启动视频详解：启动分析+N项操作实例
  18. 「mysql优化专题」优化之路高级进阶——表的设计及优化（6）
  19. 制作centos的启动盘
  20. spring定时任务详解（@Scheduled注解）

热门文章

  1. 5款极简极美WordPress主题，亲测可用附送源码
  2. Centos7 密钥对登陆（适用于群晖DSM）
  3. 【Redis3.0.x】事务
  4. 那些最全面的Windows10安装pytorch踩过的坑以及如何应用
  5. 【Docker】Docker概述、理解docker的集装箱、标准化、隔离的思想、 docker出现解决了什么问题
  6. 【ORA】ORA-27125:unable to create shared memory segment
  7. Flink源码剖析：Jar包任务提交流程
  8. cursor pin s和cursor pin s wait on x
  9. Windows10下Canvas对象获得屏幕坐标不正确的原因排查与处理
  10. postgres模糊匹配大杀器