次小生成树的两种算法

                int
                 Kruskal_MinTree()
{
    
                int
                 u,v;
    init();
    
                int
                 i,flag,cnt;
    minedge = 0;
    flag = cnt = 0;
    int tmp = 0;
    for(i=0;i<m;i++)
    {
        u = edge[i].s;
        v = edge[i].t;
        int fx = findset(u);
        int fy = findset(v);
        if(fx != fy)
        {
            use[minedge++] = i;
            tmp += edge[i].w;
            fa[fx] = fy;
            cnt++;
        }
        if(cnt == n-1)
        {
            flag = 1;   //找到最小生成树break;
        }
    }
    if(flag)
        return tmp;
    return -1;   //不存在最小生成树，返回-1}

int Sec_MinTree()
{
    int i,j,mini,tmp;
    int cnt,flag,u,v;
    mini = Mod;
    for(i=0;i<minedge;i++)   //枚举最小生成树中的每条边，将其去除    {
        init();
        flag = cnt = tmp = 0;
        for(j=0;j<m;j++)
        {
            if(j != use[i])  //去除边            {
                u = edge[j].s;
                v = edge[j].t;
                int fx = findset(u);
                int fy = findset(v);
                if(fx != fy)
                {
                    cnt++;
                    tmp += edge[j].w;
                    fa[fx] = fy;
                }
                if(cnt == n-1)
                {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag && tmp < mini)
            mini = tmp;
    }
    if(mini == Mod)
        mini = -1;
    return mini;
}

                int
                 fa[N];

                const
                int M = 100010struct Edge
{
    int u,v,w;
    bool chose;
}edge[M];

struct Adge
{
    int v,next;
}G[N];        //边数组int tot,n,m;
int first[N];  //邻接表头节点位置int end[N];    //邻接表尾节点位置int mp[N][N];  //任意两点在最小生成树路径上的最长边长int findset(int x)
{
    if(x != fa[x])
        fa[x] = findset(fa[x]);
    return fa[x];
}

int cmp(Edge ka,Edge kb)
{
    if(ka.w != kb.w)
        return ka.w < kb.w;
    if(ka.u != kb.u)
        return ka.u < kb.u;
    return ka.v < kb.v;
}

void Kruskal(Edge *edge)
{
    int k = 0;
    int i,w,v;
    //初始化邻接表，对于每个节点添加一条指向其自身的边，表示以i为代表元的集合只有点ifor(tot=0;tot<n;tot++)
    {
        G[tot].v = tot+1;
        G[tot].next = first[tot+1];
        end[tot+1] = tot;
        first[tot+1] = tot;
    }
    sort(edge+1,edge+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(k == n-1)
            break;
        if(edge[i].w < 0)
            continue;
        int fx = findset(edge[i].u)
        int fy = findset(edge[i].v);
        if(fx != fy)   //修改部分，遍历两个点所在集合        {
            for(w=first[fx];w!=-1;w=G[w].next)
            {
                for(v=first[fy];v!=-1;v=G[v].next)
                {
                    //每次合并两个等价类的时候，分别属于两个等价类的两点间的最长边一定是当前加入的边
                    mp[G[w].v][G[v].v] = mp[G[v].v][G[w].v] = edge[i].w;
                }
            }
            //合并两个邻接链表
            G[end[fy]].next = first[fx];
            end[fy] = end[fx];
            fa[fx] = fy;
            k++;
            edge[i].chose = 1;
        }
    }
}

int main()
{
    //初始化建图int mst,secmst;
    Kruskal(edge);
    mst = 0;
    for(i=1;i<=m;i++)
        if(edge[i].chose)
            mst += edge[i].w;
    secmst = INF;
    for(i=1;i<=m;i++)
    {
        if(!edge[i].chose)
        {
            secmst = min(secmst,mst+edge[i].w-mp[edge[i].u][edge[i].v]);
        }
    }
    return0;
}