Description

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值) 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

Output

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

Sample Input

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

Sample Output

11

HINT

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

 

题解

就是求严格次小生成树

目前常见做法是先用Kurskal求出最小生成树

然后枚举不在树上的边，试着把它连到树上，找到形成的环上边权最大但不等于新加的边权的一条边，计算出（最小生成树权值+新加边边权-找到的最大）

对每条不在最小生成树上的边计算过之后再取min就是结果

而要求形成的环上边权最大但不等于新加的边权的一条边，我们就可以用树剖维护一个最大值和次大值，然后就可以轻松（mlog²n）得出答案了

我才不会说我边权转化成点权的时候没按dfn序结果调了一整天也没发现呢，哼

代码

//by 减维#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long long#define ls l,mid,v<<1#define rs mid+1,r,v<<1|1#define getm mid=(l+r)>>1using namespace std;struct us{ int x,y; ll v;}edg[300005];struct edge{ int to,ne; ll v;}e[200005];int n,m,num,ecnt,fa[100005],dep[100005],siz[100005],son[100005],val[100005];int f[100005],dfn[100005],out[100005],head[100005],top[100005];long long ans1,ans2,ans,ma[400005],ma2[400005];bool pd[300005];ll inf=1ll<<62;bool cmp(const us&x,const us&y){ return x.v
             
              y;}int find(int x){ if(x==fa[x])return x; fa[x]=find(fa[x]); return fa[x];}void add(int x,int y,int z){ e[++ecnt].to=y; e[ecnt].ne=head[x]; e[ecnt].v=z; head[x]=ecnt;}void df1(int x){ dep[x]=dep[f[x]]+1; siz[x]=1; for(int i=head[x];i;i=e[i].ne) { int dd=e[i].to; if(dd==f[x])continue; f[dd]=x; df1(dd); siz[x]+=siz[dd]; if(!son[x]||siz[son[x]]
              
               dep[top[y]]){ tmp=max(tmp,ask(1,num,1,dfn[top[x]],dfn[x],edg[i].v)); x=f[top[x]]; }else { tmp=max(tmp,ask(1,num,1,dfn[top[y]],dfn[y],edg[i].v)); y=f[top[y]]; } } int lca=dep[x]
               
                dep[y]?x:y; if(x!=y)tmp=max(tmp,ask(1,num,1,dfn[son[lca]],dfn[deper],edg[i].v)); ans2=min(ans2,ans1-tmp+edg[i].v); } printf("%lld",ans2);}
               
              
             
            
           
          
         
        
       
      
     

还有一种类型题，本质上还是求次小生成树 

【题目背景】

HJZ 买了一套新房子，他正在为新房子的装修发愁。

【题目描述】

土豪 HJZ 的新房子需要铺设水管网。 水管网一共有 n 个点，其中 1 号点是进水口，其余 n − 1 个点是出水口。

房子预留 了 m 根水管的空间，每根水管可以连接两个点，但要花费一定的代价。

现在 HJZ 想知道让所有出水口都直接或间接与进水口联通的最小代价。

由于装修 过程中可能会出现一些玄学事件，他还想知道代价最小的连接方案是否唯一。保证存在 一种连接方案。

【输入格式】

从文件 pipe.in 中读入数据。

第一行一个正整数 T 表示测试数据组数。

对于每一组测试数据：

• 第一行两个整数 n, m 分别表示水管网的点数和预留的管道数。

• 接下来 m 行，每行三个正整数 a, b, c 表示一条连接 a, b 的双向管道需要 c 的 代价。

【输出格式】 输出到文件 pipe.out 中。 对于每一组测试数据，分别输出两行。

第一行一个整数表示最小代价。 第二行一个字符串 Yes 或 No 表示连接方案是否唯一。 

这道题当时考试的时候一时脑抽。。。就写出来了一个二分。。。留在这里当做纪念吧。。。

//by 减维#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include