题目描述

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 E_MEM​ ，严格次小生成树选择的边集是 E_SES​ ，那么需要满足：\sum _{e \in E_S} value(e) < \sum _{e \in E_M} value(e)∑e∈ES​​value(e)<∑e∈EM​​value(e) 。

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入格式

第一行包含两个整数 nn 和 mm ，表示无向图的点数与边数。

接下来 mm 行，每行3个数 x,y,zx,y,z 表示，点 xx 和点 yy 之间有一条边，边的权值为 zz 。

输出格式

包含一行，仅一个数，表示严格次小生成树的边权和。

---

solution

 

次小生成树与最小生成树一定只差一条边。

如果差两条，我们一定可以把一条换回去。

那么就先求出最小生成树，枚举非树边，找它在树上连成的环上的最小值替代即可。

由于要严格次小，所以还得维护次小值，分讨即可。

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define maxn 500005using namespace std;int n,m,head[maxn],tot,fl[maxn];int par[maxn],deep[maxn];long long ans;struct node{ int u,v,w,nex;}e[maxn*2],E[maxn];struct no{ int f,m1,m2;}st[maxn][22];bool cmp(node a,node b){ return a.w
                
                 =0;x--){ if(deep[st[u][x].f]>=deep[v]){ A=merge(A,st[u][x]); u=st[u][x].f; } } for(int x=20;x>=0;x--){ if(st[u][x].f!=st[v][x].f){ A=merge(A,st[u][x]);A=merge(A,st[v][x]); u=st[u][x].f,v=st[v][x].f; } } if(u==v)return A; A=merge(A,st[u][0]);A=merge(A,st[v][0]); return A;}int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w); } Kruskal(); dfs(1,0); for(int j=1;j<=20;j++) for(int i=1;i<=n;i++){ st[i][j]=merge(st[i][j-1],st[st[i][j-1].f][j-1]); } //for(int i=1;i<=n;i++)printf("%d %d %d\n",st[i][1].f,st[i][1].m1,st[i][1].m2);puts(""); int M=1e9; for(int i=1;i<=m;i++){ if(fl[i])continue; int u=E[i].u,v=E[i].v; no tmp=get(u,v); if(tmp.m1