小 \(C\) 最近学了很多最小生成树的算法，\(Prim\) 算法、\(Kurskal\) 算法、消圈算法等等。 正当小 \(C\) 洋洋得意之时，小 \(P\) 又来泼小 \(C\) 冷水了。小 \(P\) 说，让小 \(C\) 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 \(EM\)，严格次小生成树选择的边集是 \(ES\)，那么需要满足： (\(value(e)\) 表示边 \(e\) 的权值) 这下小 \(C\) 蒙了，他找到了你，希望你帮他解决这个问题。
第一行包含两个整数 \(N\) 和 \(M\)，表示无向图的点数与边数。 接下来 \(M\) 行，每行 3 个数 $ 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
数据中无向图无自环； \(50\%\) 的数据 \(N \leq 2 000\) ,\(M \leq 3 000\)； \(80\%\) 的数据 \(N \leq 50 000\), \(M \leq 100 000\)； \(100\%\) 的数据 \(N\leq 100 000\),\(M\leq 300 000\) ，边权值非负且不超过 \(10^9\) 。
首先有一个我并不会证的结论，（严格）次小生成树一定是最小生成树加一条边再删一条边得到的。
回忆非严格次小生成树的做法，先处理出最小生成树上任意两点之间的路径上的最大值，然后枚举添加每一条不在最小生成树上的边 \((u,v)\) ，删掉原树上 \(u\) 到 \(v\) 路径上的最大值，然后把这条边加入就可以了。
严格最小生成树与它不同的一点是，我们找的 “原树上 \(u\) 到 \(v\) 路径上的最大值” 必须小于 我们要加的边的边权。 于是用树上倍增 \(lca\) 来求树上每两点间路径上的最大值和次大值就好了。
求次大值是个坑，每次我都有考虑不到的地方……一定要注意注意注意！ 调了好久，我好弱啊……
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N = 100005; typedef long long ll; struct node{ int v,len; node *next; }pool[N*2],*h[N]; int cnt; void addedge(int u,int v,int len){ node *p=&pool[++cnt],*q=&pool[++cnt]; p->v=v;p->next=h[u];h[u]=p;p->len=len; q->v=u;q->next=h[v];h[v]=q;q->len=len; } int n,m; int f[N][20],fmax[N][20],gmax[N][20],dep[N]; void dfs(int u){ int v; for(node *p=h[u];p;p=p->next) if(!dep[v=p->v]){ dep[v]=dep[u]+1; f[v][0]=u; fmax[v][0]=p->len; gmax[v][0]=0; for(int j=1;j<20;j++){ f[v][j]=f[f[v][j-1]][j-1]; fmax[v][j]=max(fmax[v][j-1],fmax[f[v][j-1]][j-1]); if(fmax[v][j-1]==fmax[f[v][j-1]][j-1]) gmax[v][j]=max(gmax[v][j-1],gmax[f[v][j-1]][j-1]); else { gmax[v][j]=min(fmax[v][j-1],fmax[f[v][j-1]][j-1]); gmax[v][j]=max(gmax[v][j],max(gmax[v][j-1],gmax[f[v][j-1]][j-1])); } } dfs(v); } } int m1,m2; inline void cg(int x,int i){ if(fmax[x][i]>m1) m2=max(m1,gmax[x][i]),m1=max(m1,fmax[x][i]); else if(fmax[x][i]<m1) m2=max(m2,fmax[x][i]); else m2=max(m2,gmax[x][i]); } void getMax(int x,int y){ m1=m2=0; if(dep[x]<dep[y]) swap(x,y); for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) cg(x,i),x=f[x][i]; if(x==y) return; for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]){ cg(x,i); cg(y,i); x=f[x][i]; y=f[y][i]; } cg(x,0); cg(y,0); } struct edge{ int u,v,len,vis; bool operator < (const edge &b) const{ return len<b.len; } }ed[N*3]; int fa[N]; inline int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); } void unit(int x,int y){ x=getfa(x); y=getfa(y); fa[x]=y; } int main() { ll ans=0; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].len); sort(ed,ed+m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=0;i<m;i++) if(getfa(ed[i].u)!=getfa(ed[i].v)){ ed[i].vis=1; ans+=ed[i].len; unit(ed[i].u,ed[i].v); addedge(ed[i].u,ed[i].v,ed[i].len); } dep[1]=1; dfs(1); int Mx=2*1e9; for(int i=0;i<m;i++) if(!ed[i].vis){ getMax(ed[i].u,ed[i].v); if(m1==ed[i].len) Mx=min(Mx,ed[i].len-m2); else Mx=min(Mx,ed[i].len-m1); } printf("%lld\n",ans+Mx); return 0; }转载于:https://www.cnblogs.com/lindalee/p/9839154.html
相关资源：数据结构—成绩单生成器