题目描述
给出一张图，求它的严格次小生成树。
思路
我们考虑最小生成树和严格次小生成树的关系，由于它只要求出边权和，所以我们可以只求出一种最小生成树。我们假如已知最小生成树T，那么其中一种严格次小生成树必定是断掉T一条边，再加入连接T1、T2的第二边权的边，这样必定有一种是次小生成树。或者说，我们不断尝试加入一条边，这样就和最小生成树形成一棵基环树，我们从环中去掉最长的一条边（除加入的边），这样也会有一种是次小生成树。
我们先来证明算法思路的正确性。首先，对于第一种思路我们很容易证明这一定还是一棵生成树，而对于每两个连通支的合并，除一次合并外选择都是最小边权，所以必定有一次合并会是次小生成树。而对于第二种思路，它也肯定是一棵生成树，我们也是类似的思想，相当于在prim时除一条边外选择了次小边，所以也是一棵次小生成树。其实两个思路本质是相同的。
求次小生成树算法：①Kruskal；②倍增；③Prim。
基本的公式是SecondMST=min(MST+w(u, v)-Max(u, v)) ((u, v)不属于MST)
我们先讲倍增的思路。加入我们加入了（u，v），我们必定要找到形成环上的的最大边和严格次大边，这样如果这条边的边权等于最大边就删去次大边，否则就删去最大边。对于求这个我们可以用倍增维护，每次维护最大边时比较简单，而次大边需要分两种：如果最大边相同，就取次大边中较大值；否则就取较小的最大边和另一个次大边中的较大值。
再说prim和Kruskal的思路。它们的基本思想都是在进行最小生成树时维护一个Max数组，表示最小生成树上两点路径上的最大边权。其实这个和倍增是有所重叠的，因为树上两点的边权可以用倍增求。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=600,MAXM=1e4+10; const ll INF=(1LL<<50); struct Edge { int x,y,w; }e[MAXM]; int fa[MAXN],nxt[MAXM],head[MAXN],to[MAXM],w[MAXM]; int f[MAXN][21],dep[MAXN],tot; ll g[MAXN][21][2]; bool used[MAXM]; bool cmp(Edge x,Edge y) { return x.w<y.w; } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void add_edge(int x,int y,int v) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w[tot]=v; } int cal(int x,int k) { int y=f[x][k]; if(g[x][k][0]==g[y][k][0]) return max(g[x][k][1],g[y][k][1]); else if(g[x][k][0]<g[y][k][0]) return max(g[x][k][0],g[y][k][1]); else return max(g[x][k][1],g[y][k][0]); } void dfs(int u,int father) { dep[u]=dep[father]+1; for(int i=0;i<=19;i++) { f[u][i+1]=f[f[u][i]][i]; g[u][i+1][0]=max(g[u][i][0],g[f[u][i]][i][0]); g[u][i+1][1]=cal(u,i); } for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(v==father)continue ; f[v][0]=u; g[v][0][0]=w[i]; g[v][0][1]=-INF; dfs(v,u); } } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=20;i>=0;i--) { if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y)return x; } for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } return f[x][0]; } ll qmax(int x,int y,int w) { ll res=-INF; for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) { if(w!=g[x][i][0])res=max(res,g[x][i][0]); else res=max(res,g[x][i][1]); x=f[x][i]; } return res; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w); sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) fa[i]=i; int cnt=0;tot=0; ll sum=0; for(int i=1;i<=m;i++) { int fx=find(e[i].x),fy=find(e[i].y); if(fx!=fy) { fa[fx]=fy; cnt++; add_edge(e[i].x,e[i].y,e[i].w); add_edge(e[i].y,e[i].x,e[i].w); used[i]=1; sum+=e[i].w; if(cnt==n-1)break ; } } dfs(1,0); ll ans=INF; for(int i=1;i<=m;i++) if(!used[i]) { int lca=LCA(e[i].x,e[i].y); int val=max(qmax(e[i].x,lca,e[i].w),qmax(e[i].y,lca,e[i].w)); ans=min(ans,sum-val+e[i].w); } printf("%lld",ans); return 0; }