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

全栈程序员-站长 • 2022年8月10日下午8:36 • 未分类 • 阅读 3

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

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

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

输入格式
第一行包含两个整数 N 和 M。

接下来 M 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之前存在一条边，边的权值为 z。

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

数据范围
N≤105,M≤3×105

#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;
}