次小生成树

别人都写最小生成树，我来个次小的，您可别看是次小，可是比最小生成树难了不少。（虽然可能对于某个强的了不得的大佬（点击进入翻译）来说，他应该会很“傲慢”的说：“这不很简单吗”） 当时五一我在QBXT上课的时候这个题我想了几想我才想出来的。

下面我给出代码（不会前向星和并查集的去看我的其他博客）

以下代码是在Kruskal算法的基础上进行修改，加入对x，y两点在最小生成树上路径中最长边的计算，存入length[ ][ ]数组。使用链式前向星记录每个集合都有哪些点。为了合并方便，除了head[ ]记录每条邻接表的头节点的位置外，end[ ]记录每条邻接表尾节点的位置便于两条邻接表合并。mst为最小生成树的大小，seemst为次小生成树的大小。在存在权值相同的边的情况下，seemst有可能等于mst。

并查集部分代码略详见我的另一篇博客（在此只给出声明）

1 //并查集部分 
2 const int maxn = 1010;
3 int UFSTree[maxn];
4 int find(int x);
5 void merge(int x , int y);

并查集

下面是Kruskal部分

 1 //kruskal
 2 const int maxe = 100010;
 3 struct node{
 4     int a , b;
 5     int w;
 6     bool select;
 7 }edge[maxe];
 8 
 9 bool cmp(node a , node b){
10     if(a.w != b.w) return a.w < b.w;
11     if(a.a != b.a) return a.a < b.a;
12     return a.b < b.b;
13 } 
14 
15 //链式前向星的数据结构
16 struct node1{
17     int to;
18     int next;
19 }; 
20 
21 node1 link[maxn];        //边数组 
22 int il;                    //边数组中数据的个数 
23 int head[maxn];            //邻接表的头节点位置 
24 int end[maxn];            //邻接表的尾节点位置 
25 int length[maxn][maxn];    //每两点在最小生成树上路径中最长的边
26 void kruskal(node * edge , int  n , int m){
27     int k = 0;
28     int  i , x , y;
29     int w , v;
30     /* 初始化邻接表，对于每个节点添加一条指向其自身的边，
31     表示以i为代表元的集合只有点i */
32     for(il = 0 ; il < n ; il ++){
33         link[il].to = il + 1;
34         link[il].next = head[il + 1];
35         end[il + 1] = il;
36         head[il + 1] = il;
37     } 
38     sort(edge + 1 , edge + 1 + m , cmp);
39     for(i = 1 ; i <= m ; i ++){
40         if(k == n - 1)break;
41         if(edge[i].w < 0)continue;
42         x = find(edge[i].a);
43         y = find(edge[i].b);
44         if(x != y){
45             //修改部分，遍历两个节点所有的集合
46             for(w = head[x] ; w != -1 ; w = link[w].next){
47                 for(v = head[y] ; v != -1 ; ){
48                     /*每次合并两个等价类的时候，分别属于两个等价类的两个
49                     点间的最长边一定是当前加入的边*/
50                     length[link[w].to][link[v].to] = length[link[v].to][link[w].to] = edge[i].w;
51                 }
52             } 
53             //合并两个邻接表
54             link[end[y]].next = head[x];
55             end[y] = end[x];
56             merge(x , y);
57             k ++;
58             edge[i].select = 1;
59         }
60     }
61 } 
62 int main(){
63     //先初始化和建图，然后进行下面的操作
64     int mst , secmst;
65     kruskal(edge , n , m );
66     mst = 0;
67     for(i = 1 ; i  <= m ; i ++){
68         if(edge[i].select)mst += edge[i].w;
69     }
70     secmst = INF;
71     for(i = 1 ; i <= m ; i ++){
72         if(! edge[i].select)secmst = min (secmst , mst + edge[i].w - length[edge[i].a][edge[i].b]);
73     }
74 }

Kruskal

整个算法运行了一次Kruskal 算法，时间复杂是O(m log m)，同时又对整个length[ ][ ] 进行赋值，时间复杂度为O(n²)，最终又进行了时间复杂度为O(m)的遍历，总的时间复杂度为O(m log m + n²)。

大佬推荐ZHT大佬