关键词：
对边建点，原图中的边转化为 点的点 - 边的点 - 点的点
于是用 LCT 维护连通关系，并支持查询最大值位置即可
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int n,m,val[N],t1,t2,t3;
namespace lct
int top, q[N], ch[N][2], fa[N], rev[N];
int mx[N];
inline void pushup(int x)
int v=max(val[x], max(val[mx[ch[x][0]]],val[mx[ch[x][1]]]));
mx[x]=x;
if(v==val[mx[ch[x][0]]]) mx[x]=mx[ch[x][0]];
if(v==val[mx[ch[x][1]]]) mx[x]=mx[ch[x][1]];
inline void pushdown(int x)
if(!rev[x]) return;
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]^=1;
swap(ch[x][0],ch[x][1]);
inline bool isroot(int x)
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
inline void rotate(int p)
int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
ch[q][x]=ch[p][x^1]; fa[ch[q][x]]=q;
ch[p][x^1]=q; fa[q]=p; fa[p]=y;
if(y) if(ch[y][0]==q) ch[y][0]=p;
else if(ch[y][1]==q) ch[y][1]=p;
pushup(q); pushup(p);
inline void splay(int x)
q[top=1]=x;
for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
for(int i=top;i;i--) pushdown(q[i]);
for(;!isroot(x);rotate(x))
if(!isroot(fa[x]))
rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);
void access(int x)
for(int t=0;x;t=x,x=fa[x])
splay(x),ch[x][1]=t,pushup(x);
void makeroot(int x)
access(x);
splay(x);
rev[x]^=1;
int find(int x)
access(x);
splay(x);
while(ch[x][0]) x=ch[x][0];
return x;
void split(int x,int y)
makeroot(x);
access(y);
splay(y);
void cut(int x,int y)
split(x,y);
if(ch[y][0]==x)
ch[y][0]=0, fa[x]=0;
void link(int x,int y)
makeroot(x);
fa[x]=y;
int query(int x,int y)
split(x,y);
return mx[y];
int ei[N],ej[N];
signed main()
ios::sync_with_stdio(false);
cin>>n>>m;
int ans=0;
for(int i=1;i<=m;i++)
cin>>t1>>t2>>t3;
val[i+n]=t3;
ei[i]=t1;
ej[i]=t2;
if(lct::find(t1)!=lct::find(t2))
lct::link(t1,n+i);
lct::link(t2,n+i);
ans+=t3;
else
int mp=lct::query(t1,t2);
if(val[mp]>t3)
lct::cut(mp,ei[mp-n]);
lct::cut(mp,ej[mp-n]);
ans-=val[mp];
lct::link(t1,n+i);
lct::link(t2,n+i);
ans+=t3;
cout<<ans<<endl;
kruskal算法求最小生成树(代码片段)
Kruskal算法求最小生成树·在这里插入代码片//struct1.structedges2.输入边3.初始化并查集4.给边排序5.然后从小到大归并边要求不连通使用并查集来判断是否联通6.比较cnt与n的大小#include<iostream>#include<algorithm>usingnamespacestd;consti... 查看详情
最小生成树(代码片段)
这篇博客是关于图论中的最小生成树，在这里我们先简单介绍最小生成树的概念：一个图中，选取总代价最小的边使得所有点都连通。由此得到的结果必然是一棵树，同时需要注意一个图的最小生成树不具有唯一性。下面介... 查看详情
最小生成树模板题p1692(代码片段)
...连通无向简单图，请你完成下列任务：任务1、求边权和最小的生成树（最小生成树）任务2、求边权和最大的生成树（最大生成树）任务3、求最大边最小的生成树（瓶颈生成树）任务4、求最小边最大的生成树（瓶颈生成树）Input... 查看详情
prim求最小生成树(代码片段)
一直以来只会Kruskalprim和dijkstra很像只不过prim维护的是最短的边，而dijkstra维护的是最短的从起点到一个点的路径同时prim要注意当前拓展的边是没有拓展过的可以用堆优化#include<bits/stdc++.h>#defineREP(i,a,b)for(registerinti=(a);i<(b);... 查看详情
1141.局域网最小生成树(代码片段)
https://www.acwing.com/problem/content/description/1143/求这个图的每个联通块内，求一颗最小生成树，相当于求原图的"最小生成深林"#include<bits/stdc++.h>usingnamespacestd;constintN=210;intn,m,sum;in 查看详情
严格次小生成树(代码片段)
...@滑翔翼我过了！！！感动中国！！！111.前置算法kruskal求最小生成树倍增求LCA2.定义次小生成树，顾名思义，边权值和大于等于最小生成树的边权和且边权和最小的生成树而严格次小生成树，就是边权值和严格大于最小生成树的... 查看详情
最小生成树(代码片段)
...sp;给定一个无向图，每条边有一个非负权值。求这个图中最小生成树的所有边的权值之和。生成树是指包含图中所有节点的一棵树，而最小生成树则指一棵所有边的权值之和最小的生成树。 输入 第... 查看详情
p2502[haoi2006]旅行-最小生成树最小比值生成树（雾(代码片段)
...求maxw和minw->枚举minw求maxw由于从S到T的路径上的最大值最小的边一定在最小生成树上（最小生成树的瓶颈路性质），所以我们可以将边从小到大排序，每次枚举边(e_i)，并将剩下的(e_i,e_ 查看详情
bor?vka算法求mst最小生成树(代码片段)
...则检测这条边连接的两个子树，如果是连接这两个子树的最小边，则更新(合并)。时间复杂度平均(O(V+E))，最坏(O((V+E)logV))。下面是Bor?vka算法演示动图：（源：Wikimedia）程序代码：structnodeintx,y,w;edge[M];in 查看详情
bzoj千题计划322：bzoj2561:最小生成树（最小割）(代码片段)
...//www.lydsy.com/JudgeOnline/problem.php?id=2561 考虑Kruscal算法求最小生成树的流程如果u和v之间的长为L的边能出现在最小生成树里，说明<L的边不能时u和v联通即求图中只存在<L的边时，u和v的最小割如果u和v之间的长为L的边能出现... 查看详情
859.kruskal算法求最小生成树（模板）(代码片段)
...无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。给定一张边带权的无向图G=(V,E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。由V中的全... 查看详情
kruskal算法求最小生成树(代码片段)
Kruskal算法：使用并查集求最小生成树，引入parent数组 1#include<iostream>2#include<vector>3#include<queue>4#include<string>5#include<climits>67usingnamespacestd;89structEdgeNode1011intsrc;12intdest;13intweight;14//自定义优先级：w... 查看详情
浅谈图论——最小生成树(代码片段)
写在前面：今天突然发现还没有写过最小生成树的博客，然后调堆优化prim板子好久才调出来……赶紧写篇博客来保命。 一、最小生成树概念：在一个n个点的有向图中，选取n-1条边使所有顶点两两联通，那么这个边集叫做这... 查看详情
最小生成树-kruskal算法(代码片段)
...是包含图的所有顶点的连通无环子图。加权连通图的一棵最小生成树是图的一棵权重最小的生成树，其中，树的权重定义为所有边的权重总和。最小生成树问题就是求一个给定的加权连通图的最小生成树问题。最小生成树的算法... 查看详情
图的最小生成树（普利姆prim算法）(代码片段)
...中的全部顶点，但只有足以构成一棵树的n-1条边。什么是最小生成树？在一个连通图的所有生成树中，各边的代价之和最小的那棵生成树称为该连通图的最小代价生成树（MST）， 简称最小生成树。求最小生成树有两种算法，... 查看详情
最小生成树(代码片段)
目录Prim、Kruskal算法求解最小生成树Prime算法2.Kruskal算法Prim、Kruskal算法求解最小生成树关于最小生成树有两个很重要的算法：Prime(普利姆)算法和Kruskal(克鲁斯卡尔)算法，下面是这两个算法的代码上的基本实现：Prime算法该算法利... 查看详情
hdu4126_hdu4756_求最小生成树的最佳替换边_kruskalandprim(代码片段)
...n(3000)个点的图，q次询问，每次询问增大一条边的权值后最小生成树的值是多少，求答案期望。第二题：?给定一张n(1000)个点的图，某两个点间的边可能不存在，问各种情况最小生成树的最大值 查看详情
图的应用——最小生成树(代码片段)
一、最小生成树先明白生成树的概念:对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。那么，在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树（MST）。如下... 查看详情