题目链接AcWing链接https://www.acwing.com/problem/content/description/358/洛谷链接https://www.luogu.com.cn/problem/P4180涉及知识1.最小生成树和 Kruskal 算法2.倍增法求最近公共祖先LCA3.图论和图论建模思路分析题面非常直白就是需要求严格次小生成树。首先我们需要回顾求严格次小生成树的通法我们设Δ \DeltaΔ为严格次小生成树相比最小生成树的边权增量则Δ w 非树边 − w 删除边 \Deltaw_{非树边}-w_{删除边}Δw非树边​−w删除边​我们的目的就是找到Δ \DeltaΔ的最小值且保证Δ 0 \Delta 0Δ0即可求出严格次小生成树。因此我们不难发现可以将所有边分为树边和非树边在求出最小生成树后枚举所有的非树边并对相应的路径进行删改。由于题目要求的严格次小性对于删除边我们至多只需要用到两点间的最大边权和次大边权。具体求解通法步骤如下首先求一遍最小生成树被选择的边为树边其他即为非树边。在最小生成树中记点a aa和b bb的路径上存在的最大边权为d 1 [ a ] [ b ] d_1[a][b]d1​[a][b]次大边权为d 2 [ a ] [ b ] d_2[a][b]d2​[a][b]再然后我们遍历所有的非树边设这条非树边连接点a aa和b bb边权为w ww。如果w d 1 [ a ] [ b ] wd_1[a][b]wd1​[a][b]则删去a aa和b bb的路径上的最大边用当前枚举到的非树边取代如果w ≠ d 1 [ a ] [ b ] w \neq d_1[a][b]wd1​[a][b]但是w d 2 [ a ] [ b ] wd_2[a][b]wd2​[a][b]则删去a aa和b bb的路径上的次大边用当前枚举到的非树边取代。这一步在代码实现中体现为对总边权值的加减每次进行删改边后得到的新权值记为r e s resres。依此类推在枚举时不断比大小得到最小的r e s resres即为严格次小生成树的总边权值。如果我们在代码实现时选择纯粹的枚举换边暴力做法则对于如本题的大数据范围就会超时基于此我们引入倍增法求最近公共祖先进行优化。首先大体的解题框架不变即跑最小生成树预处理最大边权和次大边权数组枚举换边算最小值。但是我们在预处理和枚举换边两步时可以利用倍增法求最近公共祖先有效降低时间复杂度。具体地暴力做法是通过深搜一层层遍历通过不断的大小比较求出任意两点间路径上的最大边权和次大边权而如果引入LCA则可以变成求点a aa和b bb各自往上跳2 k 2^k2k步时后的最大边权和最小边权记作d 1 [ a 或 b ] [ k ] d_1[a或b][k]d1​[a或b][k]和d 2 [ a 或 b ] [ k ] d_2[a或b][k]d2​[a或b][k]一直跳到最近公共祖先即可。具体实现路径为将预处理最大边权和次大边权数组这一步融入倍增法LCA的预处理中每跳到一层在更新d e p t h depthdepth和f a fafa数组的同时也对d 1 [ a 或 b ] [ k ] d_1[a或b][k]d1​[a或b][k]和d 2 [ a 或 b ] [ k ] d_2[a或b][k]d2​[a或b][k]进行更新枚举换边时对于每一条连接a aa和b bb边权为w ww的非树边在跳步求最近公共祖先的同时将跳到每一步时的最大边权和次大边权都记录在同一个数组中找到最大值和次大值然后再比较w ww和最大边权和次大边权的大小关系算出边权的增量Δ \DeltaΔ。之后再按照传统方法得出最小生成树总边权值和增量之和的最小值。AC代码#includeiostream#includecstring#includealgorithm#includequeueusingnamespacestd;typedeflonglongLL;constintN1e510,M3e510,INF0x3f3f3f3f;structEdge{inta,b,c;boolused0;booloperator(constEdget)const{returnct.c;}}edges[M];intn,m;intne[M],h[N],w[M],e[M],idx;intdepth[N],fa[N][17],d1[N][17],d2[N][17];intp[N];voidadd(inta,intb,intc){e[idx]b;w[idx]c;ne[idx]h[a];h[a]idx;return;}intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}LLkruskal(){LL res0;sort(edges1,edges1m);for(inti1;in;i)p[i]i;for(inti1;im;i){intaedges[i].a,bedges[i].b,cedges[i].c;afind(a),bfind(b);if(a!b){p[a]b;resc;edges[i].usedtrue;}}returnres;}voidbuild(){memset(h,-1,sizeofh);for(inti1;im;i){intaedges[i].a,bedges[i].b,cedges[i].c;if(edges[i].used){add(a,b,c);add(b,a,c);}}return;}//预处理voidbfs(){memset(depth,INF,sizeofdepth);depth[0]0,depth[1]1;queueintq;q.push(1);while(!q.empty()){intnowq.front();q.pop();for(intih[now];i!-1;ine[i]){intje[i];if(depth[j]depth[now]1){depth[j]depth[now]1;fa[j][0]now;q.push(j);d1[j][0]w[i],d2[j][0]-INF;for(intk1;k16;k){intancfa[j][k-1];fa[j][k]fa[anc][k-1];intdistance[4]{d1[j][k-1],d2[j][k-1],d1[anc][k-1],d2[anc][k-1]};d1[j][k]d2[j][k]-INF;for(intu0;u4;u){intnowddistance[u];if(nowdd1[j][k])d2[j][k]d1[j][k],d1[j][k]nowd;elseif(nowd!d1[j][k]nowdd2[j][k])d2[j][k]nowd;}}}}}return;}intlca(inta,intb,intw){intdistance[M];intcnt0;if(depth[a]depth[b])swap(a,b);for(intk16;k0;k--){if(depth[fa[a][k]]depth[b]){distance[cnt]d1[a][k];distance[cnt]d2[a][k];afa[a][k];}}if(a!b){for(intk16;k0;k--){if(fa[a][k]!fa[b][k]){distance[cnt]d1[a][k];distance[cnt]d2[a][k];distance[cnt]d1[b][k];distance[cnt]d2[b][k];afa[a][k];bfa[b][k];}}distance[cnt]d1[a][0];distance[cnt]d1[b][0];}intdis1-INF,dis2-INF;for(inti1;icnt;i){if(distance[i]dis1)dis2dis1,dis1distance[i];elseif(distance[i]!dis1distance[i]dis2)dis2distance[i];}if(wdis1)returnw-dis1;if(wdis2)returnw-dis2;returnINF;}intmain(){scanf(%d%d,n,m);for(inti1;im;i){inta,b,c;scanf(%d%d%d,a,b,c);edges[i]{a,b,c};}LL sumkruskal();build();//建边bfs();//预处理各种数组LL res1e18;for(inti1;im;i){if(!edges[i].used){intaedges[i].a,bedges[i].b,cedges[i].c;intdifferencelca(a,b,c);resmin(res,sumdifference);}}coutresendl;return0;}