[图论]次小生成树

注意

• SMST::weight 直接记录了最小生成树的权重
• 对于平行边/自环要进行特殊处理

说明

1. 求最小生成树时，用数组maxd[i][j]来表示MST中i到j最大边权
2. 求完后，直接枚举所有不在MST中的边，替换掉最大边权的边，更新答案

使用方法

1. `SMST::init(n); `
2. SMST::adde(u, v, w);初始化顶点个数，起始点位置
3. int status = SMST::smst(); 返回-1表示无最小生成树，返回-2表示有最小生成树无 次小生成树，否则返回次小生成树的权

模板

邻接表

// 顶点下标1～n
const int Vmax = 105;
namespace SMST
{
    struct Edge
    {
        int u,v,next,w,vis;
    }e[405];
    int ecnt;
    int he[Vmax];
    // MST
    int n;//n个顶点
    int s;//起点 树的根
    int weight; //MST的重量
    int dis[Vmax]; //dis[i]表示指向i点的最短的边
    bool vis[Vmax]; //标记该点是否在树上
    int pre[Vmax];//记录前驱
    //SMST
    int subweight; //SMST的重量
    int id[Vmax];
    int maxd[Vmax][Vmax]; //maxd[u][v]表示 u-v路径上最大的边权
    void init(int Vsz,int source=1)//默认起点为1
    {
        memset(he,-1,sizeof(he));
        ecnt=0;
        memset(dis,INF,sizeof(dis));
        memset(maxd,0,sizeof(maxd));
        memset(vis,false,sizeof(vis));
        n=Vsz;
        weight=0;
        dis[source]=0;
        pre[source]=source;
        s=source;
    }

    //1~n的邻接矩阵
    void adde(int u,int v,int w)
    {
        e[ecnt].vis=0;
        e[ecnt].u=u;
        e[ecnt].v=v;
        e[ecnt].w=w;
        e[ecnt].next=he[u];
        he[u]=ecnt++;
    }

    int prim()
    {
        /*
        返回值说明：
            -1: 无生成树
            weight: 最小生成树的重量
        */
        for(int i=1;i<=n;i++)
        {
            int pos=0;
            int minc = INF;
            for(int j=1;j<=n;j++)
            {
                if(!vis[j]&&dis[j]<minc)
                {
                    pos=j;
                    minc=dis[j];
                }
            }
            if(minc==INF) return -1; //n个点不联通 无生成树
            weight+=dis[pos];
            vis[pos]=true;
            if(i!=s)
            {
                e[id[pos]].vis=1;
                e[id[pos]^1].vis=1;
            }
            for(int j=1;j<=n;j++)
            {
                if(j==pos)    continue;
                if(vis[j])
                    maxd[j][pos]=maxd[pos][j]=max(dis[pos],maxd[j][pre[pos]]);
            }
            for(int j=he[pos];j!=-1;j=e[j].next)
            {
                int v=e[j].v;
                if(!vis[v] && e[j].w<dis[v])
                {
                    dis[v]=e[j].w;
                    pre[v]=pos;
                    id[v]=j;
                }
            }
        }
        return weight;
    }
    int smst()
    {
    /*
    返回值说明：
        -1: 无生成树
        -2: 有最小生成树 无次小生成树 （比如给出的图即为一棵树）
        subweight: 次小生成树的重量
    */
        if(prim()==-1)    return -1; //无生成树
        subweight=INF;
        for (int i=0;i<ecnt;i+=2)
        {
            int u=e[i].u;
            int v=e[i].v;
            if(e[i].vis == 0)
                subweight=min(subweight,weight+e[i].w-maxd[u][v]);
        }
        if(subweight==INF)    return -2; //只有唯一生成树 也就是说只有最小生成树没有次小生成树
        return subweight;
    }
}

邻接矩阵

无法处理平行边

// 顶点下标1～n
const int Vmax = 1005;
namespace SMST
{
    // MST
    int n;//n个顶点
    int s;//起点 树的根
    int weight; //MST的重量
    int mp[Vmax][Vmax];
    int dis[Vmax]; //dis[i]表示指向i点的最短的边
    bool vis[Vmax]; //标记该点是否在树上
    int pre[Vmax];//记录前驱
    //SMST
    int subweight; //SMST的重量
    bool used[Vmax][Vmax]; //表示当前边有没有被用过
    int maxd[Vmax][Vmax]; //maxd[u][v]表示 u-v路径上最大的边权

    void init(int Vsz,int source=1)//默认起点为1
    {
        memset(mp,INF,sizeof(mp));
        memset(dis,INF,sizeof(dis));
        memset(used,0,sizeof(used));
        memset(maxd,0,sizeof(maxd));
        memset(vis,false,sizeof(vis));
        n=Vsz;
        for(int i=0;i<=n;i++)
            mp[i][i]=0;
        weight=0;
        dis[source]=0;
        pre[source]=source;
    }

    //1~n的邻接矩阵
    void adde(int u,int v,int w)
    {
        mp[u][v]=w;
        mp[v][u]=w;
    }

    int prim()
    {
        /*
        返回值说明：
            -1: 无生成树
            weight: 最小生成树的重量
        */
        for(int i=1;i<=n;i++)
        {
            int pos=0;
            int minc=INF;
            for(int j=1;j<=n;j++)
            {
                if(!vis[j]&&dis[j]<minc)
                {
                    pos=j;
                    minc=dis[j];
                }
            }
            if(minc=INF) return -1; //n个点不联通 无生成树
            weight+=dis[pos];
            used[pos][pre[pos]]=true; // for SMST
            used[pre[pos]][pos]=true; // for SMST
            vis[pos]=true;
            for(int j=1;j<=n;j++)
            {
                if(j==pos) continue;
                if(vis[j])
                    maxd[j][pos]=maxd[pos][j]=max(dis[pos],maxd[j][pre[pos]]);
                else if(!vis[j]&&mp[pos][j]<dis[j])
                {
                    dis[j]=mp[pos][j];
                    pre[j]=pos;
                }
            }
        }
        return weight;
    }

    int smst()
    {
        /*
        返回值说明：
            -1: 无生成树
            -2: 有最小生成树 无次小生成树 （比如给出的图即为一棵树）
            subweight: 次小生成树的重量
        */
        if(prim()==-1)    return -1; //无生成树
        subweight=INF;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(mp[i][j]!=INF && !used[i][j])
                    subweight=min(subweight,weight+mp[i][j]-maxd[i][j]);
        if(subweight==INF)    return -2; //只有唯一生成树 也就是说只有最小生成树没有次小生成树
        return subweight;
    }
}