「一本通 4.4 例 4」次小生成树

题目描述
原题来自：BeiJing 2010 组队赛

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

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

输入格式
第一行包含两个整数 和 ，表示无向图的点数与边数；

接下来 行，每行三个数 ，表示点 和点 之间有一条边，边的权值为 。

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

数据保证必定存在严格次小生成树。

样例
样例输入
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
样例输出
11
数据范围与提示
对于全部数据，，数据中无向图无自环，边权值非负且不超过 。

首先最小生成树肯定是n - 1条边的连通图， 那么用并查集求的最小生成树没有被选的边肯定大于等于最小生成树中最大的边 。（最小生成树中的边集为S ， 没有被选的边集为T）
求次小生成树也就是将剩下没有被选的其中一条边替换最小生成树中其中一条边
贪心考虑：用T里面的一条边a替换S中的一条边b， b是s中最大的， 如果b == a ， 那么就替换s中次小的边，否则就替换b
但是呢， 如果在最小生成树中加入一条边， 就会出现一个环， 也就是说我们加入一条边会出现一条环， 那么我们就要将环中的一条第二大的边去掉，第一大的为新加入的，那么就每次考虑T中的每条边， 求该边联通的一个环中的次大，树上倍增求解。

 #include 
using namespace std ;
const int N = 2e5 + 10 ;
typedef long long ll ;
const int INF = 0x3f3f3f3f ;
struct node
{
  int u , v , w ;
  node () {}
  node (int u , int v , int w) :u(u) , v(v) , w(w) {}
  bool operator<(const node &a) const {
    return w < a.w ;
  }
}edge[N << 1];
int fa[N] , f[N][21] , vis[N] ;
int n , m ;
int find(int x)
{
  return fa[x] == x ? x : fa[x] = find(fa[x]) ;
}
int cd[N][21] , zd[N][21] , idx , e[N] , ne[N] , w[N] , h[N] ;
void add(int a , int b , int c)
{
  e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx ++ ;
}
int deep[N] ;
void dfs(int u , int faa)
{
  deep[u] = deep[faa] + 1 ;
  f[u][0] = faa ;
  for(int i = h[u] ; ~i ; i = ne[i])
   {
     if(e[i] == faa) continue ;
     zd[e[i]][0] = w[i] ;
     cd[e[i]][0] = -INF ;
     dfs(e[i] , u) ;
   }
}
void init()
{
  for(int i = 1 ;i <= 19 ;i ++)
   {
     for(int j = 1 ; j <= n ;j ++)
      {
        f[j][i] = f[f[j][i - 1]][i - 1] ;
        zd[j][i] = max(zd[j][i - 1] , zd[f[j][i - 1]][i - 1]) ;
        cd[j][i] = max(cd[j][i - 1] , cd[f[j][i - 1]][i - 1]) ;
        if(zd[j][i - 1] < zd[f[j][i - 1]][i - 1])
         cd[j][i] = max(cd[j][i] , zd[j][i - 1]) ;
        else if(zd[f[j][i - 1]][i - 1] < zd[j][i - 1])
         cd[j][i] = max(cd[j][i] , zd[f[j][i - 1]][i - 1]) ;
      }
   }
   return ;
}
int lca(int a , int b)
{
  if(deep[a] < deep[b]) swap(a , b) ;
  for(int i = 19 ;i >= 0 ;i --)
   if(deep[f[a][i]] >= deep[b])
    a = f[a][i] ;
  if(a == b) return a ;
  for(int i = 19 ;i >= 0 ;i --)
   if(f[a][i] != f[b][i])
    a = f[a][i] , b = f[b][i] ;
  return f[a][0] ;
}
int ask(int x , int y , int z)
{
  int ans = 0 ;
  for(int i = 19 ;i >= 0 ;i --)
   if(deep[f[x][i]] >= deep[y])
    {
      if(zd[x][i] < z)
       ans = max(ans , zd[x][i]) ;
      else ans = max(ans , cd[x][i]) ;
      x = f[x][i] ;
    }
    return ans ;
}
int main()
{
  scanf("%d%d" , &n , &m) ;
  for(int i = 1; i <= n ;i ++) fa[i] = i ;
  for(int i = 1; i <= m ;i ++)
   {
     int u , v , w ;
     scanf("%d%d%d" , &u , &v , &w) ;
     edge[i] = {u , v , w } ;
   }
   memset(h , -1 , sizeof h) ;
   sort(edge + 1 , edge + m + 1) ;
   ll w = 0 ;
   for(int i = 1; i <= m ;i ++)
    {
      int fu = find(edge[i].u) , fv = find(edge[i].v) ;
      if(fu != fv)
       {
         w += edge[i].w ;
         fa[fu] = fv ;
         vis[i] = 1;
         add(edge[i].u , edge[i].v , edge[i].w) ;
         add(edge[i].v , edge[i].u , edge[i].w) ;
       }
    }
    dfs(1 , 0) ;
    init() ;
    ll ans = 1e18 ;
    for(int i = 1; i <= m ;i ++)
     {
       if(!vis[i])
        {
          int x = edge[i].u , y = edge[i].v  ;
          int z = lca(x , y) ;
          int t1 = ask(x , z , edge[i].w ) , t2 = ask(y , z , edge[i].w) ;
          ans = min(ans , w - max(ask(x , z , edge[i].w) , ask(y , z , edge[i].w)) + edge[i].w) ;
        }
     }
     cout << ans << endl ;
  return 0 ;
}