当前位置：首页 > news >正文

次小生成树模板

news 来源：原创 2024/4/25 0:19:34

次小生成树可由最小生成树换一条边得到，这是核心结论!

证明:换种方式去看待这个结论(一个生成树可以通过换边得到另一个生成树)，T是某一棵最小生成树，T0是任一棵异于T的生成树，通过变换T0 --> T1 --> T2 --> ... --> Tn (T) 变成最小生成树。所谓的变换是，每次把Ti中的某条边换成T中的一条边, 而且树T(i+1)的权小于等于Ti的权。

         看下面的具体步骤(一定要理解透彻)。
         step 1. 在Ti中任取一条不在T中的边uv.
         step 2. 把边uv去掉，就剩下两个连通分量A和B，在T中，必有唯一的边u'v' 连结A和B。这是为什么呢？因为生成树中任意两点间只有一条路径(下面也要用这个)，且必有一条。
         step 3. 显然u'v'的权比uv小 (prime算法贪心的，否则,uv就应该在T中)，把u'v'替换uv即得树T(i+1)。
         特别地：取T0为任一棵次小生成树，T(n-1) 也就是次小生成树且跟T差一条边，结论得证。

 1 #include<stdio.h>       ////O（v^2）,适用于稠密图
 2 #include<string.h>
 3 #define max(x,y) x>y?x:y
 4 #define min(x,y) x<y?x:y
 5 const int N=1000;
 6 const int INF=0x3f3f3f3f;
 7 int a[N][N],p[N],low[N],n;
 8 int f[N][N],fa[N];
 9 int prim()
10 {
11     int i,j,ans=0,poi,top=0,sta[N];
12     memset(p,0,sizeof(p));
13     memset(f,0,sizeof(f));
14     p[1]=1,sta[++top]=1;
15     for(i=1;i<=n;i++)
16     {
17         low[i]=a[1][i];
18         fa[i]=1;        //父节点
19     }
20     for(i=1;i<n;i++)           ////n-1次操作
21     {
22         int mi=INF;
23         for(j=1;j<=n;j++)
24         {
25             if(!p[j]&&mi>low[j])
26             {
27                 mi=low[j];
28                 poi=j;
29             }
30         }
31         p[poi]=1;
32         ans+=mi;
33         //// dp
34         for(j=1;j<=top;j++)
35         {
36             f[sta[j]][poi]=f[poi][sta[j]]=max(mi,f[fa[poi]][sta[j]]);
37         }
38         sta[++top]=poi;
39         for(j=1;j<=n;j++)
40             if(!p[j]&&low[j]>a[poi][j])
41             {
42                 fa[j]=poi;  ////更新父节点
43                 low[j]=a[poi][j];
44             }
45     }
46     return ans;
47 }
48 int SMST()
49 {
50     int tmp=prim(),i,j,mi=INF;
51     printf("SMT: %d\n",tmp);
52     for(i=1;i<=n;i++)
53     {
54         for(j=1;j<=n;j++)
55         {
56             if(i!=j&&a[i][j]!=INF&&fa[i]!=j&&fa[j]!=i)  ////fa[i]!=j&&fa[j]!=i表示这两个点之间的边没有在最小生成树中
57             {
58                 mi=min(mi,a[i][j]-f[i][j]);
59             }
60         }
61     }
62     return tmp+mi;
63 }
64 int main()
65 {
66     int i,j;
67     while(scanf("%d",&n)!=EOF)
68     {
69         for(i=1;i<=n;i++)
70             for(j=1;j<=n;j++)
71                 scanf("%d",&a[i][j]);
72         printf("SMST: %d\n",SMST());
73     }
74     return 0;
75 }
76 /* 测试数据
77 4
78 0 4 9 21
79 4 0 8 17
80 9 8 0 16
81 21 17 16 0
82 */