『OI笔记』次小生成树

前置芝士

• 一点点图论芝士
• Kruskal（或者你用Prim也行），用来求最小生成树

定义

定义就是字面意思，无需解释。

思路

先将输入的图的最小生成树求出来，再枚举没有增加过的边，将他们加入到最小生成树当中去。新增一条边之后，我们就可以得到一个基环树。   接下来，我们在这棵基环树上找到环，并删除环上最长的边，这是我们就可以得到一颗新的树。通过枚举每一颗新的树，找到这些树中的最小的树，这就是最终的次小生成树了。

具体步骤

¶Step 1

首先当然是要跑一遍kruskal拉！ :idea:

¶Step 2

我们要解决一个问题：那就是如何快速地找到环上最大的边？当然是预处理了。所以，我们可以在Kruskal（Prim党自便）求最小生成树的时候顺便存一下两点之间的最长路径。   怎么存？由于Kruskal和Prim的算法原理有些不同，所以Prim的同学可以先退场了。由于我们只是要求两个点所在的环上的最长边，所以就等于在这两个点合并前时候他们所在的子集的最长边。   所以，我们就要储存好该集合（树）下所有的点。这个不难，用vector就可以了。还有，因为kruskal在开始加边前经过sort，所以在后面出现的边的边权一定大于前面出现的，所以直接等于就可以了。转存的代码如下：

//更新最大值
//gra是用来存集合（树）中的点的
int l1=gra[x].size();
int l2=gra[y].size();
for (int p=0;p<l1;p++)
    for (int q=0;q<l2;q++)
        mx[gra[x][p]][gra[y][q]]=mx[gra[y][q]][gra[x][p]]=edge[i].s;

//合并时需要将被合并的点所在的集合的所有点进行合并（有绕口令内味了bushi）
fa[x]=y;
for (int j=0;j<l1;j++)
    gra[y].push_back(gra[x][j]);

注意，以上代码是在kruskal里边的！！

¶Step 3

最后统计答案的时候，新建一个ans，原来最小生成树的权值和就用sum把。我们按照思路上的，枚举每一个不再最小生成树中的边，然后对ans进行更新就OK了！

void output()
{
    int ans=INT_MAX;
    for (int i=1;i<=m;i++)
    {
        if (edge[i].vis) continue;
        ans=min(ans,sum+edge[i].s-mx[edge[i].u][edge[i].v]);
    }
    if (ans==sum) 
        cout<<"Not Unique!"<<endl;
    else cout<<sum<<endl;
}

例题及代码

POJ 1679 The Unique MST POJ不给用万能头文件大大的差评！XPINXPINXPINXPINXPINXPINXPIN

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f

终 THE END