一、总体思路
首先,我这一题的思路是倍增LCA+Kruskal
首先,kruskal求最小生成树 不会的戳这里
求次小生成树 倍增 LCA
关键在于次小生成树怎么求:
问自己一些问题
怎么求不严格次小生成树
不严格次小生成树为什么不严格
方法每次选择U—V之间的边,前提是最小生成树上不存在的边,添边之后删去较短边,使用LCA找到祖先,删边,这里保证次小生成树的是?只要添得边不是U-V在树上最小距离即可。
模板
#include
#include
#include
#include
typedef long long ll;
using namespace std;
const int M=1e5+100;
ll n,m,res,ans=0x3f3f3f3f,mx;
int f[M],fa[25][M],dep[M];
ll d[2][25][M];
bool used[3*M],vis[M];
vectora[M];
struct Edge{
int from, to;
ll val;
bool operator return val }
}e[3*M];
int F(int x){
if(f[x]==x) return x;
return f[x]=F(f[x]);
}
void kruskal(){ //kruskal 算最大生成树(已保证任意两点之间最小限重最优)
sort(e,e+m); int lef=n-1;
for(int i=1;i for(int i=0;iint x=F(e[i].from),y=F(e[i].to);
if(x!=y){
f[x]=y; res+=e[i].val;
used[i]=1; --lef;
mx=max(mx , e[i].val);
}
}
}
void dfs(int x){ //深搜建树(可能不止一棵,因为数据未保证是连通图)
vis[x]=true;
for(int i=1;i fa[i][x]=fa[i-1][fa[i-1][x]];
ll t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];
d[0][i][x]=max(t1 , t2);
d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);
if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));
}
for(int i=0;i int t=e[a[x][i]].to+e[a[x][i]].from-x;
if(vis[t]) continue; //vis为1表示是父节点
dep[t]=dep[x]+1; fa[0][t]=x;
d[0][0][t]=e[a[x][i]].val; dfs(t);
}
}
int lca(int u,int v){
if(dep[u]swap(u,v);
if(dep[u]!=dep[v]){ //将深度做相等
for(int i=23,h=dep[u]-dep[v];i>=0;--i)
if(h&(1 }
if(u==v) return u; //如果已经在一个节点上就直接返回
for(int i=23;i>=0;--i) if(fa[i][u]!=fa[i][v])
u=fa[i][u] , v=fa[i][v];
return fa[0][u];
}
ll get(int u,int v,int c){
int fht=lca(u,v);
ll m1=0,m2=0;
for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht];i>=0;--i){
if(h1&(1 if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];
else if(d[0][i][u]>m2) m2=d[0][i][u];
else m2=max(m2 , d[1][i][u]);
} if(h2&(1 if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];
else if(d[0][i][v]>m2) m2=d[0][i][v];
else m2=max(m2 , d[1][i][v]);
}
} if(m1==c) return c-m2;
else return c-m1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;iint u,v; ll w;
scanf("%d%d%lld",&u,&v,&w);
e[i].from=u;
e[i].to=v;
e[i].val=w;
} kruskal();
for(int i=0;ia[e[i].from].push_back(i);
a[e[i].to].push_back(i);
} dep[1]=1; dfs(1);
for(int i=0;iif(e[i].val-mx>ans) break;
ll t=get(e[i].from , e[i].to , e[i].val);
ans=min(ans , t);
} return printf("%lldn",res+ans),0;