最小生成树的个数_最小生成树的两种算法

最小生成树的个数_最小生成树的两种算法给定一张 N 个点 M 条边的无向图,求无向图的严格次小生成树。设最小生成树的边权之和为 sum,严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。输入格式第一行包含两个整数 N 和 M。接下来 M 行,每行包含三个整数 x,y,z,表示点 x 和点 y 之前存在一条边,边的权值为 z。输出格式包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)数据范围N≤105,M≤3×105输入样例:5 61 2 11 3 22 4 33 5 4

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一张 N 个点 M 条边的无向图,求无向图的严格次小生成树。

设最小生成树的边权之和为 sum,严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。

输入格式
第一行包含两个整数 N 和 M。

接下来 M 行,每行包含三个整数 x,y,z,表示点 x 和点 y 之前存在一条边,边的权值为 z。

输出格式
包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

数据范围
N≤105,M≤3×105

输入样例:
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
输出样例:
11
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 3 * 3e5 + 10;
const int maxbit = 20;
typedef long long ll;
int f[N][maxbit],d1[N][maxbit],d2[N][maxbit],height[N];
struct Edge{ 
   
    int u,v,w,next;
    bool f;
    bool operator<(const Edge a)const{ 
   
        return w < a.w;
    }
}edge[M];
int head[N],cnt;
int n,m;
int fa[N];
int Find(int x){ 
   
    return fa[x] = (fa[x] == x ? x : Find(fa[x]));
}
void add(int u,int v,int w){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
void dfs(int u,int fa,int d,int w){ 
   
    f[u][0] = fa;
    height[u] = d;
    d1[u][0] = w,d2[u][0] = 0;
    for(int i = 1;i <= maxbit - 1;i ++){ 
   
        f[u][i] = f[f[u][i - 1]][i - 1];
        d1[u][i] = max(d1[u][i - 1],d1[f[u][i - 1]][i - 1]);
        if(d1[u][i - 1] == d1[f[u][i - 1]][i - 1])
            d2[u][i] = max(d2[u][i - 1],d2[f[u][i - 1]][i - 1]);
        if(d1[u][i - 1] > d1[f[u][i - 1]][i - 1])
            d2[u][i] = max(d1[f[u][i - 1]][i - 1],d2[u][i - 1]);
        else d2[u][i] = max(d1[u][i - 1],d2[f[u][i - 1]][i - 1]);
    }
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v,ww = edge[i].w;
        if(v == fa)continue;
        dfs(v,u,d + 1,ww);
    }
}
int lca(int x,int y,int &a,int &b){ 
   
    a = b = 0;
    if(height[x] < height[y])swap(x,y);
    for(int i = maxbit - 1;i >= 0;i --){ 
   
        if(height[f[x][i]] >= height[y]){ 
   
            if(d1[x][i] > a)b = a,a = d1[x][i];
            else if(d1[x][i] != a && d1[x][i] > b)b = d1[x][i]; 
            if(d2[x][i] > a)b = a,a = d2[x][i];
            else if(d2[x][i] != a && d2[x][i] > b)b = d2[x][i];
            x = f[x][i];
        }
    }
    if(x == y)return x;
    for(int i = maxbit - 1;i >= 0;i --){ 
   
        if(f[x][i] != f[y][i]){ 
   
            int aa = d1[x][i],bb = d2[x][i],cc = d1[y][i],dd = d2[y][i];
            if(aa > a)b = a,a = aa;
            else if(aa != a && aa > b)b = aa;
            if(bb > a)b = a,a = bb;
            else if(bb != a && bb > b)b = bb; 
            if(cc > a)b = a,a = cc;
            else if(cc != a && cc > b)b = cc; 
            if(dd > a)b = a,a = dd;
            else if(dd != a && dd > b)b = dd; 
            x = f[x][i],y = f[y][i];
        }
    }
    int aa = d1[x][0],bb = d2[x][0],cc = d1[y][0],dd = d2[y][0];
    if(aa > a)b = a,a = aa;
    else if(aa != a && aa > b)b = aa;
    if(bb > a)b = a,a = bb;
    else if(bb != a && bb > b)b = bb; 
    if(cc > a)b = a,a = cc;
    else if(cc != a && cc > b)b = cc; 
    if(dd > a)b = a,a = dd;
    else if(dd != a && dd > b)b = dd; 
    return f[x][0];
}
int main(){ 
   
    memset(head,-1,sizeof head);
    cin>>n>>m;
    int x,y,w;
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y>>w;
        edge[i].u = x,edge[i].v = y,edge[i].w = w;
        edge[i].f = false;
    }
    cnt = m;
    sort(edge,edge + m);
    for(int i = 0;i <= n;i ++)fa[i] = i;
    ll res = 0;
    for(int i = 0;i < m;i ++){ 
   
        int a = Find(edge[i].u),b = Find(edge[i].v),w = edge[i].w;
        if(a != b){ 
   
            fa[a] = b;
            edge[i].f = true;
            add(edge[i].u,edge[i].v,w),add(edge[i].v,edge[i].u,w);
            res += w;
        }
    }
    
    dfs(1,0,1,0);
    int xx,yy;
    ll t = 0x3f3f3f3f3f3f3f3f;
    for(int i = 0;i < m;i ++){ 
   
        if(!edge[i].f){ 
   
            int a = edge[i].u,b = edge[i].v,w = edge[i].w;
            int aa = 0,bb = 0;
            lca(a,b,aa,bb);
            if(aa == w){ 
   
                t = min(res + w - bb,t);
            }
            else t = min(res + w - aa,t);
        }
    }
    cout<<t<<endl;
    
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168625.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mysql基础

    mysql基础mysql基础

  • JAVA位移运算「建议收藏」

    JAVA位移运算「建议收藏」1、java将负整数转成二进制这里以8位为例,只是为了表明过程,实际中java的int类型是4byte,也就是32位。二进制的首位是符号位,0表示正数,1表示负数,在java中,会对负数进行取反加一操作,进而计算出实际的十进制值。如10101010,此8位的二进制数首位是1,表示负数,所以对后面的七位进行取反加一操作,即0101010–>1010110,换成十进制的数就是86,再加上首位的1表示负数,结果就是-86。2、位移运算1)正数的右移:如10>>2,左边自动补0,右边移出

  • tar压缩和解压文件或文件夹

    1. 使用tar压缩文件tar-zcvftest.tar.gz./test/该命令表示压缩当前文件夹下的文件夹test,压缩后缀名为test.tar.gz如果不需要压缩成gz,只需要后缀为tar格式的,那么输入如下命令:tar-cvftest.tar./test/ 2. 使用tar解压文件tar-xzvftest.tar.gz  该命令表示把后缀为….

  • 国家信息中心数据恢复中心官网_stn源源

    国家信息中心数据恢复中心官网_stn源源写在前面:目前在学习pytorch官方文档的内容,以此来记录自己的学习过程,本次学习的是STN网络。传送门:官方文档中文翻译STN论文链接(SpatialTransformerNetworks)为什么要用到STN网络呢:卷积神经网络定义了一个异常强大的模型类,但在计算和参数有效的方式下仍然受限于对输入数据的空间不变性。在此引入了一个新的可学模块,空间变换网络,它显式地允许在网络中对数据进行空间变换操作。这个可微的模块可以插入到现有的卷积架构中,使神经网络能够主动地在空间上转换特征映射,在特征

  • C# FindWindowEx用法

    C# FindWindowEx用法2010-11-2809:51:18|  分类: 程序编程|字号 订阅 函数功能:该函数获得一个窗口的句柄,该窗口的类名和窗口名与给定的字符串相匹配。这个函数查找子窗口,从排在给定的子窗口后面的下一个子窗口开始。在查找时不区分大小写。   函数原型:HWNDFindWindowEx(HWNDhwndParent,HWNDhwndChildAfter

  • 在c语言里0和1表示什么_’0’是什么意思c语言

    在c语言里0和1表示什么_’0’是什么意思c语言C语言中常见~Number,怎么计算?计算一个数字的~number比如说现在有A=60那么A的8位二进制数就是00111100那首先要计算~A即~60,那么先取反即11000011。因为负数的补码是取反+1。所以此处逆向操作需要-1取反即11000011-1==11000010(第一步逆向操作)11000010=>取反=>00111101=>十进制的61最后结果A==60,~A=-61C

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号