次小生成树（信息学奥赛一本通 1555）

题目描述

原题来自：BeiJing 2010 组队赛给定一张 N 个点 M 条边的无向图，求无向图的严格次小生成树。设最小生成树的边权之和为 sum，严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。

输入格式

第一行包含两个整数 N 和 M，表示无向图的点数与边数；接下来 MM 行，每行三个数 x,y,z，表示点 x 和点 y 之间有一条边，边的权值为 z。

输出格式

包含一行，仅一个数，表示严格次小生成树的边权和。

数据保证必定存在严格次小生成树。

样例

样例输入

5 6 
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6

样例输出

11

数据范围与提示

对于全部数据，1≤N≤10^5,1≤M≤3×10^5，数据中无向图无自环，边权值非负且不超过 10^9。

--->题目是从别处复制过来的，因为ybt网站实在是太乐色了，，，直接复制过来的话格式会全乱掉（辣鸡(┬＿┬)↘

先来发表一下做题感受：哇做这道题真的是心累，（因为蒟蒻总是这里错一点那里错一点），光调试就花了我...近2h（我都不知道自己在肝什么）啊抓狂(ノಠ益ಠ)ノ彡┻━┻

以上均为废话（管不住自己的手...☹

刚开始拿到这道题，我是肥肠简单粗暴的想：吖既然是求次小生成树，那就暴力去搜改哪条边使得改了之后的边权之和最小（没办法蒟蒻脑子不太好使

然鹅因为这道题是放在LCA的习题里面，所以我自然而然的想到了可以运用LCA和树上倍增法的思想

先求出一棵最小生成树，设边权之和为sum，把最小生成树里的n-1条边暂时称为“树边”，其他的m-n+1条边称为“非树边”（书上就是这么写的蒟蒻有什么办法yingyingying

然后就是列举每一条“非树边”（首尾为x,y，长度为z），将其添加到最小生成树中去，设x,y之间的路径上的最大边权为v1，次大边权为v2，那么易得：

  • 如果z>v1，就可以用z换v1，此时边权和变为sum-v1+z，加入候选答案

  • 如果z=v1,就可以用z换v2，此时边权和变为sum-v2+z，加入候选答案

然后一边循环一边用ans记录最小的候选答案

在预处理部分，用f[i][j]表示i的 2的j次方辈 祖先（自动断句）

用g[i][j][0]表示从i到f[i][j]路径上的最大边权，同理，用g[i][j][1]表示次大边权，

接下来咧，就采用倍增计算LCA的框架，列举“非树边”......

然后,,,就详见代码吧

顺便提下，整个算法的时间复杂度是O（MlogN）丫，所以很轻松就AC啦

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=1e6+5,inf=0x3f3f3f3f;
  4 int next[2*N],head[2*N],to[N*2],d[N],f[N][21],fa[N],id[N],v[2*N],in[N],di[N],g[N][21][3];
  5 int n;
  6 int m,q,w,p,tot,cnt;
  7 long long sum,ans=0x7ffffffffff;
  8 struct node{
  9     int x,y,z;
 10     bool u;
 11     bool operator <(const node &b)const
 12     {
 13         return z<b.z;
 14     }
 15 }a[3*N];
 16 int read()
 17 {
 18     int f=1;char ch;
 19     while((ch=getchar())<'0'||ch>'9')
 20         if(ch=='-')f=-1;
 21     int res=ch-'0';
 22     while((ch=getchar())>='0'&&ch<='9')
 23         res=res*10+ch-'0';
 24     return res*f;
 25 }
 26 void write(int x)
 27 {
 28     if(x<0)
 29     {
 30         putchar('-');
 31         x=-x;
 32     }
 33     if(x>9)write(x/10);
 34     putchar(x%10+'0');
 35 }
 36 void add(int x,int y,int z)
 37 {
 38     next[++tot]=head[x];
 39     head[x]=tot;
 40     to[tot]=y;v[tot]=z;
 41 }
 42 
 43 void dfs(int x,int a)
 44     {
 45         f[x][0]=a; d[x]=d[a]+1;
 46         int i;
 47         for(i=head[x];i;i=next[i]) if(to[i]!=a)
 48         {
 49             g[to[i]][0][0]=v[i];
 50             g[to[i]][0][1]=-inf;
 51             dfs(to[i],x);
 52         }
 53         return;
 54     }
 55 void pre()
 56 {
 57     dfs(1,0);
 58     for(int j=1;j<=19;j++)
 59         for(int i=1;i<=n;i++)
 60         {
 61             f[i][j]=f[f[i][j-1]][j-1];
 62             g[i][j][0]=max(g[i][j-1][0],g[f[i][j-1]][j-1][0]);
 63             if(g[i][j-1][0]==g[f[i][j-1]][j-1][0])
 64                 g[i][j][1]=max(g[i][j-1][1],g[f[i][j-1]][j-1][1]);
 65             else if(g[i][j-1][0]<g[f[i][j-1]][j-1][0])
 66                 g[i][j][1]=max(g[i][j-1][0],g[f[i][j-1]][j-1][1]);
 67             else if(g[i][j-1][0]>g[f[i][j-1]][j-1][0])
 68                 g[i][j][1]=max(g[f[i][j-1]][j-1][0],g[i][j-1][1]);
 69         }
 70 }
 71 int find(int x)
 72 {
 73     return (fa[x]==x)?(x):(fa[x]=find(fa[x]));
 74 }
 75 int lca(int x,int y)
 76 {
 77     if(d[x]<d[y])swap(x,y);
 78     for(int i=20;i>=0;i--)
 79     {
 80         if(d[f[x][i]]>=d[y])x=f[x][i];
 81         if(x==y)return x;
 82     }
 83     for(int i=20;i>=0;i--)
 84     {
 85         if(f[x][i]!=f[y][i])
 86         {
 87             x=f[x][i];
 88             y=f[y][i];
 89         }
 90     }
 91     return f[x][0];
 92 }
 93 
 94 int ff(int a,int l,int z)
 95 {
 96     int x=a,y=0;
 97     for(int i=20;i>=0;i--)
 98     {
 99         if(d[f[x][i]]>=d[l])
100         {
101             if(z>g[x][i][0])y=max(y,g[x][i][0]);
102             else y=max(y,g[x][i][1]);
103             x=f[x][i];
104         }
105     }
106     return y;
107 }
108 int main()
109 {
110     n=read();m=read();
111     for(int i=1;i<=n;i++)fa[i]=i;
112     for(int i=1;i<=m;i++)
113     {
114         int x,y,z;
115         a[i].x=read();a[i].y=read();a[i].z=read();
116     }
117     sort(a+1,a+1+m);
118     int k=0;
119     for(int i=1;i<=m;i++)
120     {
121         int xx=find(a[i].x),yy=find(a[i].y);
122         if(xx==yy) continue;
123         fa[xx]=yy; sum+=a[i].z; a[i].u=1;
124         add(a[i].x,a[i].y,a[i].z); add(a[i].y,a[i].x,a[i].z);
125     }
126     pre();
127     for(int i=1;i<=m;i++)
128     {
129         if(!a[i].u)
130         {
131             int l=lca(a[i].x,a[i].y),p=ff(a[i].x,l,a[i].z),q=ff(a[i].y,l,a[i].z);
132             ans=min(ans,sum-max(p,q)+a[i].z);
133         }
134     }
135     printf("%lld",ans);
136     return 0;
137 }

最后再放上我调试过程中的代码，证明并提醒自己：找错有多不容易啊！！！

（都看到这里了，你忍心不点一个“推荐”喵o( =•ω•= )m

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=1e6+5,inf=0x3f3f3f3f;
  4 int next[2*N],head[2*N],to[N*2],d[N],f[N][21],fa[N],id[N],v[2*N],in[N],di[N],g[N][21][3];
  5 int n;
  6 int m,q,w,p,tot,cnt;
  7 long long sum,ans=0x7ffffffffff;
  8 struct node{
  9     int x,y,z;
 10     bool u;
 11     bool operator <(const node &b)const
 12     {
 13         return z<b.z;
 14     }
 15 }a[3*N];
 16 int read()
 17 {
 18     int f=1;char ch;
 19     while((ch=getchar())<'0'||ch>'9')
 20         if(ch=='-')f=-1;
 21     int res=ch-'0';
 22     while((ch=getchar())>='0'&&ch<='9')
 23         res=res*10+ch-'0';
 24     return res*f;
 25 }
 26 void write(int x)
 27 {
 28     if(x<0)
 29     {
 30         putchar('-');
 31         x=-x;
 32     }
 33     if(x>9)write(x/10);
 34     putchar(x%10+'0');
 35 }
 36 void add(int x,int y,int z)
 37 {
 38     next[++tot]=head[x];
 39     head[x]=tot;
 40     to[tot]=y;v[tot]=z;
 41     //cout<<tot<<endl;
 42 }
 43 /*void dfs(int s,int fff)
 44 {
 45     f[s][0]=fff;d[s]=d[fff]+1;
 46     //cout<<"1";
 47     for(int i=head[s];i;i=next[i])
 48     {
 49         //cout<<to[i]<<endl;
 50         if(to[i]!=fff)
 51         {
 52             g[to[i]][0][0]=v[i];
 53             g[to[i]][0][1]=-inf;
 54             //cout<<g[to[i]][0][0]<<endl;
 55             dfs(to[i],s);
 56             //w++;cout<<w<<endl;
 57         }
 58         
 59     }
 60         
 61 }*/
 62 void dfs(int x,int a)
 63     {
 64         f[x][0]=a; d[x]=d[a]+1;
 65         int i;
 66         for(i=head[x];i;i=next[i]) if(to[i]!=a)
 67         {
 68             g[to[i]][0][0]=v[i];
 69             g[to[i]][0][1]=-inf;
 70             dfs(to[i],x);
 71         }
 72         return;
 73     }
 74 void pre()
 75 {
 76     //cout<<"1";
 77     dfs(1,0);
 78     for(int j=1;j<=19;j++)
 79         for(int i=1;i<=n;i++)
 80         {
 81             f[i][j]=f[f[i][j-1]][j-1];
 82             g[i][j][0]=max(g[i][j-1][0],g[f[i][j-1]][j-1][0]);
 83             if(g[i][j-1][0]==g[f[i][j-1]][j-1][0])
 84                 g[i][j][1]=max(g[i][j-1][1],g[f[i][j-1]][j-1][1]);
 85             else if(g[i][j-1][0]<g[f[i][j-1]][j-1][0])
 86                 g[i][j][1]=max(g[i][j-1][0],g[f[i][j-1]][j-1][1]);
 87             else if(g[i][j-1][0]>g[f[i][j-1]][j-1][0])
 88                 g[i][j][1]=max(g[f[i][j-1]][j-1][0],g[i][j-1][1]);
 89             //cout<<g[i][j][1]<<' '<<g[i][j][0]<<endl;
 90         }
 91 }
 92 int find(int x)
 93 {
 94     /*if(fa[x]!=x)fa[x]=find(fa[x]);
 95     return fa[x];*/
 96     return (fa[x]==x)?(x):(fa[x]=find(fa[x]));
 97 }
 98 int lca(int x,int y)
 99 {
100     if(d[x]<d[y])swap(x,y);
101     for(int i=20;i>=0;i--)
102     {
103         if(d[f[x][i]]>=d[y])x=f[x][i];
104         if(x==y)return x;
105     }
106     for(int i=20;i>=0;i--)
107     {
108         if(f[x][i]!=f[y][i])
109         {
110             x=f[x][i];
111             y=f[y][i];
112         }
113     }
114     return f[x][0];
115 }
116 
117 int ff(int a,int l,int z)
118 {
119     int x=a,y=0;
120     for(int i=20;i>=0;i--)
121     {
122         if(d[f[x][i]]>=d[l])
123         {
124             if(z>g[x][i][0])y=max(y,g[x][i][0]);
125             else y=max(y,g[x][i][1]);
126             x=f[x][i];
127         }
128     }
129     return y;
130 }
131 int main()
132 {
133     n=read();m=read();
134     for(int i=1;i<=n;i++)fa[i]=i;
135     for(int i=1;i<=m;i++)
136     {
137         int x,y,z;
138         a[i].x=read();a[i].y=read();a[i].z=read();
139     }
140     sort(a+1,a+1+m);
141     int k=0;
142     /*for(int i=1;i<=m;i++)
143     {
144         //cout<<"1";
145         if(find(a[i].x)!=find(a[i].y))
146         {
147             fa[find(a[i].y)]=find(a[i].x);
148             k++;
149             sum+=a[i].z;
150             a[i].u=1;
151             //cout<<"1";
152             add(a[i].x,a[i].y,a[i].z);
153             add(a[i].y,a[i].x,a[i].z);
154             if(k==n-1)break;
155         }
156     }*/
157      for(int i=1;i<=m;i++)
158     {
159         int xx=find(a[i].x),yy=find(a[i].y);
160         if(xx==yy) continue;
161         fa[xx]=yy; sum+=a[i].z; a[i].u=1;
162         add(a[i].x,a[i].y,a[i].z); add(a[i].y,a[i].x,a[i].z);
163     }
164     pre();
165     /*for(int j=0;j<=2;j++)
166         for(int i=0;i<=2;i++)
167             cout<<g[i][j][0]<<' '<<g[i][j][1]<<endl;*/
168     for(int i=1;i<=m;i++)
169     {
170         if(!a[i].u)
171         {
172             int l=lca(a[i].x,a[i].y),p=ff(a[i].x,l,a[i].z),q=ff(a[i].y,l,a[i].z);
173             ans=min(ans,sum-max(p,q)+a[i].z);
174             //cout<<l<<endl;
175             //cout<<p<<' '<<q<<endl;
176         }
177     }
178     printf("%lld",ans);
179     return 0;
180 }

（还想再bb一句，传送门什么的太累了不想做了，还是去首页找找吧，在标签里看“LCA”或者“树上倍增法”应该会有你想要的

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ljy-endl/p/11367678.html