当前位置：网站首页>次小生成树【模板】

次小生成树【模板】

2022-07-27 12:59:00 【51CTO】

给一个图，判断图的最小生成树是否唯一。
End[]记录邻接表尾节点的位置。Len[x][y]表示对x，y两点在最小生成树上最长边的计算。MST表示最小生成树的大小，SecMST表示次小生成树的大小。

       
       #include<iostream>
       
#include<algorithm>
       
#include<cstdio>
       
#include<cstring>
       
using namespace std;
       
const int MAXN = 1010;  //元素个数
       
const int MAXM = 100010;
       
int father[MAXN];   
       
int find(int x) //查找x所在等价类的代表元素
       
{
       
    if(x != father[x])
       
        father[x] = find(father[x]);
       
    return father[x];
       
}
       
struct Node
       
{
       
    int from;   //边的起点
       
    int to;     //边的终点
       
    int w;      //权值
       
    bool vis;   //标记为是否是最小生成树上的边
       
};
       
Node Edges[MAXM];//存储边信息
       
bool cmp(Node a, Node b) //按边的权值排序
       
{
       
    return a.w < b.w;
       
}
       
//链式前向星记录每个集合有哪些点
       
struct Node1
       
{
       
    int to;
       
    int next;
       
};
       
Node1 Vertex[MAXN];//边数组，表示结点连向的边
       
int N,M;
       
int head[MAXN];     //邻接表头结点位置
       
int End[MAXN];      //邻接表尾结点位置，方便合并
       
int Len[MAXN][MAXN];//图中两点之间在最小生成树上路径最长的边
       
void Kruskal()
       
{
       
    int x,y,k = 0;
       
    int ans = 0;
       
    //初始化邻接表，每个节点初始的时候添加一条指向自己的边，表示结点i各自为一个集合
       
    memset(head,-1,sizeof(head));   
       
    memset(End,-1,sizeof(End));
       
    for(int i = 1; i <= N; i++)
       
    {
       
        Vertex[i].to = i;
       
        Vertex[i].next = head[i];
       
        End[i] = i;
       
        head[i] = i;
       
    }
       
    sort(Edges,Edges+M,cmp);//边按权值排序
       
    for(int i = 0; i < M; i++)
       
    {
       
        if(k == N-1)    //构成生成树
       
            break;
       
        if(Edges[i].w < 0)
       
            continue;
       
        x = find(Edges[i].from);
       
        y = find(Edges[i].to);
       
        if(x != y)
       
        {
       
            //遍历两个节点所在的集合
       
            for(int w = head[x]; w != -1; w = Vertex[w].next)
       
            {
       
                for(int v = head[y]; v != -1; v = Vertex[v].next)
       
                {
       
                    Len[Vertex[w].to][Vertex[v].to] = Len[Vertex[v].to][Vertex[w].to] = Edges[i].w;
       
                    //当前加入的边一定是加(x,y)边成环后删去的除(x,y)外长度最大的边
       
                }
       
            }
       
            //合并两个邻接表，表示两点已连边连在一个集合中，最终连成一个最小生成树
       
            Vertex[End[y]].next = head[x];
       
            head[x] = head[y];
       
            End[y] = End[x];
       
            father[y] = x;
       
            k++;
       
            Edges[i].vis = true;
       
        }
       
    }
       
}
       
int main()
       
{
       
    int T,x,y,w;
       
    scanf("%d",&T);
       
    while(T--)
       
    {
       
        scanf("%d%d",&N,&M);
       
        for(int i = 1; i <= N; i++)
       
            father[i] = i;
       
        memset(Len,0x7f,sizeof(Len));
       
        for(int i = 0; i < M; i++)
       
        {
       
            scanf("%d%d%d",&x,&y,&w);
       
            Edges[i].from = x;
       
            Edges[i].to = y;
       
            Edges[i].w = w;
       
            Edges[i].vis = false;
       
        }
       
        int MST,SecMST;//MST最小生成树大小,SecMST次小生成树大小
       
        Kruskal();
       
        MST = 0;//最小生成树长度
       
        for(int i = 0; i < M; i++)
       
        {
       
            if(Edges[i].vis)
       
                MST += Edges[i].w;
       
        }
       
        SecMST = 0xfffff0;
       
        for(int i = 0; i < M; i++)
       
        {
       
            if(!Edges[i].vis)//加边，并删去最小生成树上的边
       
                SecMST = min(SecMST,MST+Edges[i].w - Len[Edges[i].from][Edges[i].to]);
       
        }
       
        if(SecMST == MST)   //次小生成树不唯一
       
            printf("Not Unique!\n");
       
        else
       
            printf("%d\n",MST);
       
    }
       
    return 0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/ITCharge/5518637

当前位置：网站首页>次小生成树【模板】

次小生成树【模板】

边栏推荐

猜你喜欢

随机推荐