首页 > 其他分享 >P1967 [NOIP2013 提高组] 货车运输 (生成树,LCA)

P1967 [NOIP2013 提高组] 货车运输 (生成树,LCA)

时间:2023-10-13 19:23:49浏览次数:41  
标签:NOIP2013 idx int LCA 货车运输 fa ans P1967 dp

P1967 [NOIP2013 提高组] 货车运输

https://www.luogu.com.cn/problem/P1967
首先有些边是没用的(比较小的边),比如两个点之间的两条(并行的)路,只有较大的会被走到,小的不会被走,因此可以直接去除小的边,即求最大生成树。
接着做求任意两点经过的边的最小值就演变成求树上任意两点的最小树边,这个可以通过倍增求LCA实现,具体就是在倍增的时候用一个数组记录一下最值就行。\(f_{i, k}\) 表示 \(i\) 点往上跳 \(2^k\) 步所经过的最小边
注意图不一定连通

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 5, M = 1e5 + 5;
int n, m, q, fa[N], dep[N], f[N][30], dp[N][30];
int h[N], e[M], ne[M], w[M], idx;
bool vis[N];

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

struct Node {
    int a, b, w;
    bool operator<(const Node &t) const {
        return w > t.w;
    }
}p[M];

int find (int x) {
    if (x != fa[x]) fa[x] = find (fa[x]);
    return fa[x];
}

void kruscal(){
    sort (p + 1, p + m + 1);
    for (int i = 1; i <= n; i ++)    fa[i] = i;
    for (int i = 1; i <= m; i ++){
        int a = p[i].a, b = p[i].b, w = p[i].w;
        a = find(a), b = find(b);
        if (a != b)    fa[a] = b, add (a, b, w), add (b, a, w);// cout << a << ' ' << b << ' ' << w << endl;
    }
}

void dfs (int x) {
    vis[x] = true;
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        if (vis[j]) continue;
        dep[j] = dep[x] + 1;
        f[j][0] = x, dp[j][0] = w[i];
        dfs (j);
    }
}

int lca (int a, int b) {
    if (find (a) != find (b))   return -1;
    if (dep[a] < dep[b])    swap (a, b); //确保a往上跳
    int ans = 1e9;
    for (int k = 20; k >= 0; k--) {
        if (dep[f[a][k]] >= dep[b]) { //注意是>=
            ans = min (ans, dp[a][k]), a = f[a][k];
        }
    }
    if (a == b)     return ans;
    for (int k = 20; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            ans = min ({ans, dp[a][k], dp[b][k]});
            a = f[a][k], b = f[b][k];
        }
    }
    ans = min ({ans, dp[a][0], dp[b][0]});
    return ans;
}

int main () {
    memset (h, -1, sizeof h);
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        scanf ("%d%d%d", &a, &b, &c);
        p[i] = {a, b, c};
    }
    kruscal (); //最大生成树
    //memset (dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        dep[i] = 1, dfs (i);
        f[i][0] = i, dp[i][0] = 0x3f3f3f3f;
    }
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[f[j][i-1]][i-1];
            dp[j][i] = min (dp[j][i-1], dp[f[j][i-1]][i-1]);
        }
    }
    scanf ("%d", &q);
    while (q--) {
        int a, b;
        scanf ("%d%d", &a, &b);
        printf ("%d\n", lca (a, b));
    }
}

标签:NOIP2013,idx,int,LCA,货车运输,fa,ans,P1967,dp
From: https://www.cnblogs.com/CTing/p/17762929.html

相关文章

  • 6577: 暗的连锁 LCA+树上差分
    描述  Dark是一张无向图,图中有N个节点和两类边,一类边被称为主要边,而另一类被称为附加边。Dark有N–1条主要边,并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外,Dark还有M条附加边。你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边......
  • 三个主要降维技术对比介绍:PCA, LCA,SVD
    前言 本文将深入研究三种强大的降维技术——主成分分析(PCA)、线性判别分析(LDA)和奇异值分解(SVD)。我们不仅介绍这些方法的基本算法,而且提供各自的优点和缺点。本文转载自DeepHubIMBA作者:IndraneelDuttaBaruah仅用于学术分享,若侵权请联系删除欢迎关注公众号CV技术指南,专......
  • 三个主要降维技术对比介绍:PCA, LCA,SVD
    随着数据集的规模和复杂性的增长,特征或维度的数量往往变得难以处理,导致计算需求增加,潜在的过拟合和模型可解释性降低。降维技术提供了一种补救方法,它捕获数据中的基本信息,同时丢弃冗余或信息较少的特征。这个过程不仅简化了计算任务,还有助于可视化数据趋势,减轻维度诅咒的风险,并提......
  • 洛谷 P1969 [NOIP2013 提高组] 积木大赛 - 小思维
    洛谷P1969[NOIP2013提高组]积木大赛[NOIP2013提高组]积木大赛题目描述春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦,大厦可以看成由\(n\)块宽度为\(1\)的积木组成,第\(i\)块积木的最终高度需要是\(h_i\)。在搭建开始之前......
  • 浅谈关于LCA
    prologue本身只会tarjan和倍增法求LCA的,但在发现有一种神奇的\(O(1)\)查询lca的方法,时间优化很明显。mainbody倍增法先讨论倍增法,倍增法求lca是一种很常见普遍的方法,这里直接放代码了,其本身的内核就是让较低点每次都跳$2^k$步,如果跳的比另一个高了,就不跳那......
  • CAD设计软件下载-CorelCAD 2020官网版 各个版本下载
    CorelCAD2014是Corel公司推出的一款强大CAD制图工具,使用CorelCAD,用户可以轻松创建专业的CAD图形,CorelCAD使用DWG格式作为其主要的图形文件格式,最高支持版本为2014的DWG和DXF文件,提供了与全球范围内大量图形软件和建筑软件的兼容性和交换功能;新版本优化了基于功能区的用户......
  • P1967 [NOIP2013 提高组] 货车运输
    P1967[NOIP2013提高组]货车运输因为可能成环,这样可能导致到达点的最小权值不一,所以用最小生成树的方法重新建图然后我是利用倍增的思想建立从i点开始,到上面点的距离ff和最小权值ww因为最小权值不好直接建立,所以不如最后统一建立最后就是寻找最近公共祖先的模板了一组hack......
  • dfs 序 O(nlogn)-O(1) 求 LCA
    学点分树,发现不会询问复杂度\(O(1)\)的LCA。于是被迫递归式学习。我们设\(dfn_i\)表示点\(i\)在dfs过程中第几个被访问到,把点按访问到的顺序排序得到的序列叫dfs序。考虑\(u\)和\(v\)在dfs序上的位置之间的这一段序列有什么。设\(lca(u,v)=x,dfn_u<dfn_v\)。......
  • 6576: 点的距离 倍增LCA
    描述 给定一棵n个点的树,Q个询问,每次询问点x到点y两点之间的距离。 输入 第一行一个正整数n,表示这棵树有n个节点;接下来n−1行,每行两个整数x,y表示x,y之间有一条连边;然后一个整数Q,表示有Q个询问;接下来Q行每行两个整数x,y表示询问x到y的距......
  • 科技:dfn 求 LCA
    upd:2023.09.13新建非常好思路,学习自Alex_Wei。摘要使用st表维护区间内所有点的dfn最小的父节点。优点是好写、时间空间常数小。前置约定\(dfn_{i}\):\(i\)是第几个被访问的点\(sub_{i}\):以\(i\)为根的子树\(LCA\):\(\text{LCA}(u,v)\)原理dfn的性质:设\(......