最小生成树的个数_最小生成树的实际应用

最小生成树的个数_最小生成树的实际应用给定一张 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/169114.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 深入理解static关键字

    深入理解static关键字提到static关键字,相信大家都不陌生,这是相对比较难以理解的一个关键字,相信各位也都能深深感受的到!本篇文章将好好总结一下static这个关键字。文章目录1、static存在的主要意义2、static的独特之处3、静态变量和实例变量的概念4、静态变量和实例变量【重点常用】5、static静态方法6、static代码块7、static应用场景1、static存在的主要意义static的主要…

  • ExpandableListView实例(一)_数据库增删改查处理和listitem点击长按处理

    ExpandableListView实例(一)_数据库增删改查处理和listitem点击长按处理本例说明:1.实例中表现层与数据处理层分开,代码可复用性强,如果能看懂代码对算法会有提高.2.组和子条目上”点击”事件处理,能够区分操作的是组还是子条目,并且得到组和子条目的内容.3.组和子条目上”长按”事件处理,能够区分组和子条目,并且得到组和子条目的内容.4.自定义条目样式,灵活与数据库中字段绑定.5.实现对DB的增删改查,并且操作后自动刷新.6.使用数据库处理框架AH

  • Project interpreter not specified(eclipse+pydev)

    Project interpreter not specified(eclipse+pydev)

    2021年11月24日
  • Pytest(8)parametrize参数化[通俗易懂]

    Pytest(8)parametrize参数化[通俗易懂]前言当某个接口中的一个字段,里面规定的范围为1-5,你5个数字都要单独写一条测试用例,就太麻烦了,这个时候可以使用pytest.mark.parametrize装饰器可以实现测试用例参数化。官方示

  • vue查看版本号「建议收藏」

    vue查看版本号「建议收藏」vue-V或者是vue–version查询的是vue-cli的版本,也就是vue脚手架的版本,如果想要查看vue的版本,直接去项目中,找到package.json文件夹找”dependencies”然后就可以看到你装的vue的版本了”dependencies”:{“axios”:”^0.21.1″,”core-js”:”^3.6.5″,”element-ui”:”^2.14.1″,”vue”:”^2.6.11″,”vue-resource”:”^

  • 数据库优化分库分表_数据库分库分表的好处

    数据库优化分库分表_数据库分库分表的好处一.数据切分关系型数据库本身比较容易成为系统瓶颈,单机存储容量、连接数、处理能力都有限。当单表的数据量达到1000W或100G以后,由于查询维度较多,即使添加从库、优化索引,做很多操作时性能仍下降严重。此时就要考虑对其进行切分了,切分的目的就在于减少数据库的负担,缩短查询时间。数据库分布式核心内容无非就是数据切分(Sharding),以及切分后对数据的定位、整合。数据切分就是将数据分散存储到多个数据库中,使得单一数据库中的数据量变小,通过扩充主机的数量缓解单一数据库的性能问题,从而达到提升数据库操作性

发表回复

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

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