【题解】严格次小生成树

题目大意：

给定一个无向图，求出该图的次小生成树，点数 $n≤100 000$ 边数 $m≤300 000$。

首先，思考暴力做法，求出最小生成树，从图中向树中加入一条边，显然, 图中就会出现一个环，而我们只需去掉环上次大的那条边（因为，最大的那条边肯定是刚加进去的，否则就不满足最小生成树的定义）。
时间复杂度：$O(mn)$。

code：

#include <bits/stdc++.h>
#define re register
using namespace std;
int read(){
    int f=1,r=0;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r*f;
}
long long lread(){
    long long f=1,r=0;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writein(int x){write(x);putchar('\n');}
const int MAXM=300001,MAXN=100001;

int f[MAXN];

int find(int x){
    if(x!=f[x])f[x]=find(f[x]);
    return f[x];
}

void unin(int x,int y){
    x=find(x),y=find(y);
    f[x]=y;
}

struct Edge{
    int from,to;
    long long dat;
}e[MAXM],e2[MAXM];

bool cmp(const Edge &q,const Edge &p){
    return q.dat<p.dat;
}

int n,m;
int num[MAXM],res;
long long minn,ans,sum;
bool flag;

void fa(){
    for(re int i=1;i<=n;i++)
        f[i]=i;
}

void kru1(){
    fa();
    sort(e+1,e+m+1,cmp);

    int cnt=0;
    for(re int i=1;i<=m;i++){
        int x=e[i].from,y=e[i].to;
        if(find(x)!=find(y)){
            unin(x,y);
            minn+=e[i].dat;
            cnt++;num[++res]=i;
            if(cnt==n-1)
                break;
        }
    }

}

void kru2(){
    for(re int i=1;i<=res;i++){
        int k=num[i];
        fa();
        sum=0;
        int tot=0;
        for(re int j=1;j<=m;j++){
            if(j==k) continue;
            int x=e[j].from,y=e[j].to;
            if(find(x)!=find(y)){
                unin(x,y);
                sum+=e[j].dat;
                tot++;
                if(tot==n-1)
                    break;
            }
        }
        if(!flag){
            if(sum>minn)
                ans=sum,flag=1;
        }
        else if(sum<ans && sum>minn)
            ans=sum;
    }
}

int main(){
    //freopen("tree.in","r",stdin);
    //freopen("tree.out","w",stdout);
    n=read(),m=read();
    for(re int i=1;i<=m;i++)
        e[i].from=read(),e[i].to=read(),e[i].dat=lread();
    kru1();
    kru2();
    writein(ans);
    return 0;
}

60 分到手。注：某 facker zqy 的代码。

wyz：轻松 AC 的题，为什么要部分分。

我们来思考如何优化。
很显然最小生成树不能优化，每一条非树边都必须被枚举，所以我们只能在求最大值上下手了。
这时候，我们考虑树上倍增法+LCA。
但是，LCA 如何记录路径上的最大值呢？
我们使用 $w$数组记录倍增的过程，$w[i][j]$记录 $j$向上 $2^i$步中这一段路径中的最大值，而可以用 $f[i][j]$记录 $j$向上 $2^i$步到达的坐标，所以 DP 方程就呼之欲出了 $w[u][i+1]=max(w[u][i],w[f[u][i]][i])$。按照这个方案，我们就可以在 $O(n$$logn)$的时间内求出树上两点路径中边权最大值了，而这个方案将原来的一个 $n$变成了 $logn$, 就离成功又进了一步。
但是，我们的想法有一点瑕疵，在题目中要求的是严格次小，是 $<$而不是 $<=$，那怎么办呢？

wyz：你是个菜逼，这都不会

在 wyz 大佬的指导下，我们明白了，可以记录一个次大值，就可以维护了。
那么，不难得到，DP 方程就成功成为了：
当 $w[u][i]>w[f[u][i]][i]$　　$w2[u][i+1]=max(w[f[u][i]][i],w2[f[u][i]][i])$
当 $w[u][i]<w[f[u][i]][i]$　　$w2[u][i+1]=max(w[u][i],w2[f[u][i]][i])$
当 $w[u][i]=w[f[u][i]][i]]$ 直接继承上一段的就行了。
code：

#include<cstdio>
#include<algorithm>
using namespace std;

#define maxn 300003
#define INF 1000000000000000

inline int read(){
    int r=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return r*f;
}

struct E{
    int u,v,w;
    E() {}
    E(int u,int v,int w):u(u),v(v),w(w) {};
    bool operator <(const E &edge) const{
        return w<edge.w;
    }
}e[maxn];

struct G{
    struct E{
        int v,w,nxt;
        E() {}
        E(int v,int w,int nxt):v(v),w(w),nxt(nxt) {};
    }e[maxn*2];

    int s_e,head[maxn];

    inline void a_e(int u,int v,int w){
        e[++s_e]=E(v,w,head[u]);
        head[u]=s_e;
    }
}t,g;

int n,m,er[25],lg[maxn],f[maxn],dep[maxn],anc[25][maxn];

long long sum,ans=INF,dp[25][maxn][2];

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    anc[0][u]=fa;
    for(int i=t.head[u];i;i=t.e[i].nxt){
        int v=t.e[i].v,w=t.e[i].w;
        if(v==fa)continue;
        dp[0][v][0]=w;
        dp[0][v][1]=-INF;
        dfs(v,u);
    }
}

inline void init(){
    dfs(1,1);
    er[0]=1,lg[0]=-1;
    for(int i=1;i<=n;i++)lg[i]=lg[(i>>1)]+1;
    for(int i=1;i<=lg[n];i++)er[i]=er[i-1]<<1;
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j<=n;j++){
            anc[i][j]=anc[i-1][anc[i-1][j]];
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][anc[i-1][j]][0]);
            dp[i][j][1]=min(dp[i-1][j][0],dp[i-1][anc[i-1][j]][0]);
            if(dp[i][j][0]==dp[i][j][1])dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][anc[i-1][j]][1]);
        }
}

long long lca(int u,int v,long long dis){
    if(dep[u]>dep[v])swap(u,v);
    int c=dep[v]-dep[u];
    long long Max=-INF,c_Max=-INF;
    while(c){
        if(Max<dp[lg[c]][v][0])c_Max=max(Max,dp[lg[c]][v][1]),Max=dp[lg[c]][v][0];
        else if(dp[lg[c]][v][0]!=Max)c_Max=max(c_Max,dp[lg[c]][v][0]);
        else c_Max=max(c_Max,dp[lg[c]][v][1]);
        v=anc[lg[c]][v];
        c-=er[lg[c]];
    }
    if(u==v)return dis==Max?c_Max:Max;
    for(int i=lg[dep[u]];i>=0;i--){
        if(anc[i][u]==anc[i][v])continue;
        if(Max<max(dp[i][u][0],dp[i][v][0])){
            if(max(dp[i][u][0],dp[i][v][0])==min(dp[i][u][0],dp[i][v][0]))c_Max=max(Max,max(dp[i][u][1],dp[i][v][1]));
            else c_Max=max(Max,min(dp[i][u][0],dp[i][v][0]));
            Max=max(dp[i][u][0],dp[i][v][0]);
        }
        else if(max(dp[i][u][0],dp[i][v][0])!=Max)c_Max=max(c_Max,max(dp[i][u][0],dp[i][v][0]));
        else if(min(dp[i][u][0],dp[i][v][0])!=Max)c_Max=min(c_Max,max(dp[i][u][0],dp[i][v][0]));
        else c_Max=max(c_Max,max(dp[i][u][1],dp[i][v][1]));
        u=anc[i][u],v=anc[i][v];
    }
    if(Max<max(dp[0][u][0],dp[0][v][0])){
        if(max(dp[0][u][0],dp[0][v][0])==min(dp[0][u][0],dp[0][v][0]))c_Max=max(Max,max(dp[0][u][1],dp[0][v][1]));
        else c_Max=max(Max,min(dp[0][u][0],dp[0][v][0]));
        Max=max(dp[0][u][0],dp[0][v][0]);
    }
    else if(max(dp[0][u][0],dp[0][v][0])!=Max)c_Max=max(c_Max,max(dp[0][u][0],dp[0][v][0]));
    else if(min(dp[0][u][0],dp[0][v][0])!=Max)c_Max=min(c_Max,max(dp[0][u][0],dp[0][v][0]));
    else c_Max=max(c_Max,max(dp[0][u][1],dp[0][v][1]));
    return dis==Max?c_Max:Max;
}

int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        e[i]=E(u,v,w);
    }
    sort(e+1,e+1+m);
    for(int i=1,j=0;i<=m;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        int fu=find(u),fv=find(v);
        if(fu==fv){
            g.a_e(u,v,w);
            continue;
        }
        f[fu]=fv;
        sum+=w;
        j++;
        t.a_e(u,v,w);
        t.a_e(v,u,w);
    }
    init();
    for(int u=1;u<=n;u++)
        for(int i=g.head[u];i;i=g.e[i].nxt){
            int v=g.e[i].v,w=g.e[i].w;
            ans=min(ans,sum-lca(u,v,w)+w);
        }
    printf("%lld",ans);
    return 0;
}

注：AK 巨佬 wyz 的代码
最后%%%%%%wyz%%%%%%%