次小生成树_牛客博客

转同学的一个模板链接：https://blog.csdn.net/chenshibo17/article/details/81215933
细分了带重边和不带重边的。

次小生成树定义：设 G=(V,E,w)是连通的无向图，T 是图G 的一个最小生成树。如果有另一棵树T1，满足不存在树T’,ω（T’）< ω（T1），则称T1是图G的次小生成树。

上面是不说人话的版本，这里是说人话的版本：一个连通的无向图（连通图、无向图不用解释吧），有许多生成树，其中最小生成树是T，他的路径总长度ω(T)最小，现在找另一棵生成树T’，如果图中T是唯一的，那ω(T’)就是第二小的，如果T不是唯一的，那T’就是另一个T，即ω(T’) == ω(T)，T’就是次小生成树。

当然有的题可能让你求严格的次小生成树，无论T是不是唯一的，ω(T’)都是第二小的。
由此也可以看出，如果次小生成树的总权值 == 最小生成树的总权值，那该图的最小生成树有不止一棵，这可以用来判断图最小生成树的数量单复情况。

求次小生成树一般都要利用一下最小生成树，比较低效的做法是在图中遍历所有属于最小生成树的边，并把当前边从图中删掉，然后对这个缺一条边的图求一次最小生成树，就这样随着最小生成树上边的遍历经过n-1次之后，我们选那n-1棵生成树里总权值最小的就是次小生成树。

认真看完这个过程就知道了，一共相当于求了n次最小生成树，是相当暴力的做法了。。。

那考虑优化的话就是要想办法更高效地利用图的最小生成树，我们可以这样：
我们不遍历最小生成树了，我们遍历图中被最小生成树占用剩下的边，即所有不属于最小生成树的边，然后我们把当前边加到最小生成树上，显然，这个时候就会出现回路，为了使其再变回树，我们去掉回路上除了新加入的那条边剩下的边中的一条边，这样就又变回了一棵树，总权值为原总权值 + （新加入边的权值 - 去掉的边的权值）。由于我们是在最小生成树上操作的，总权值最小，新的总权值就会增大，那么,（新加入边的权值 - 去掉的边的权值）> 0 ，括号中的就是增量。我们求的是次小生成树，这样就要这个增量最小，那么在遍历的每一种情况中，我们就要去掉的边的权值最大，这样，操作就变成了：

//次小生成树的算法核心
for(遍历图中所有不属于最小生成树的边)
    把当前边加入最小生成树产生回路
    去掉回路中除当前边之外权值最大的边
    记录下现在的树及其总权值
在上面循环产生的树中选一棵总权值最小的，就是次小生成树

如果是那种求严格的次小生成树的，那在环路去边的步骤中，如果 回路中除当前边之外权值最大的边的权值 == 当前边的权值，那就去掉 回路中除当前边之外权值第二大的边。

不难看出，这个算法中，对应于第一个算法的求一次最小生成树，这里只要维护一条回路，操作量大大缩小，而这一条回路的维护可以在Prim算法中用动态规划的思想完成（具体实现见下面代码），预先处理找到回路中要去掉的那条边，那么接下来在次小生成树的算法中去掉那条边的复杂度就变成了O(1)，这些使得算法的速度大大加快。

示例代码（模板题）：

POJ 1679：

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V’, E’), with the following properties:
1. V’ = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E’) of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E’.

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string ‘Not Unique!’.

Sample Input

Sample Output

3
Not Unique!

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 111;
const int inf = 0x3f3f3f3f;
int Map[maxn][maxn];//邻接矩阵存图
int Max[maxn][maxn];//表示最小生成树中i到j的最大边权
bool used[maxn][maxn];//判断该边是否加入最小生成树
int pre[maxn];//点在最小生成树上的前驱
int dis[maxn];//在已存的点集中，到各个点的最短边
bool vis[maxn];//判断该点是否加入最小生成树
void init(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) Map[i][j] = 0;
            else Map[i][j] = inf;
}
void read(int m)
{
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        Map[u][v] = Map[v][u] = w;
    }
}
int prim(int n)
{
    int ans = 0;
    memset(vis, false, sizeof(vis));
    memset(used, false, sizeof(used));
    memset(Max, 0, sizeof(Max));
    for (int i = 2; i <= n; i++) 
    {
        dis[i] = Map[1][i];
        pre[i] = 1;
    }
    pre[1] = 0;
    dis[1] = 0;
    vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        int min_dis = inf, k;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && min_dis > dis[j])
            {
                min_dis = dis[j];
                k = j;
            }
        }
        if (min_dis == inf) return -1;//如果不存在最小生成树
        ans += min_dis;
        vis[k] = true;
        used[k][pre[k]] = used[pre[k]][k] = true;
        for (int j = 1; j <= n; j++)
        {
            if (vis[j]) Max[j][k] = Max[k][j] = max(Max[j][pre[k]], dis[k]);
            /*********** 这里加了一行dp，预处理找到树上任意两点间路径上的最大边。在以i为索引的循 环中，最小生成树会被逐渐更新完成，那么我们随着树的更新，也在更新要找的最 大边。对于一条路径，dp初始时没有边，加入一条边，那么唯一的最大边就是它， 然后新增一条边，将其边权与原路径最大边权比较，大的就是新路径的最大边权。 这里随着循环的进行，我们对所有产生的路径进行这样的操作，最终更新出任何两 点间路径上的最大边权。 ***********/
            if (!vis[j] && dis[j] > Map[k][j])
            {
                dis[j] = Map[k][j];
                pre[j] = k;
            }
        }
    }
    return ans;//最小生成树的权值之和
}
int smst(int n, int min_ans)//min_ans 是最小生成树的权值和
{
    int ans = inf;
    for (int i = 1; i <= n; i++)//枚举最小生成树之外的边
        for (int j = i + 1; j <= n; j++)
            if (Map[i][j] != inf && !used[i][j])
                ans = min(ans, min_ans + Map[i][j] - Max[i][j]);
    if (ans == inf) return -1;
    return ans;
}
void solve(int n)
{
    int ans = prim(n);
    if (ans == -1)
    {
        puts("Not Unique!");
        return;
    }
    if (smst(n, ans) == ans)
    printf("Not Unique!\n");
    else
    printf("%d\n", ans);
}

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &m);
        init(n);
        read(m);
        solve(n);
    }
    return 0;
}