https://ac.nowcoder.com/acm/contest/1057/G
/*严格次小生成树 5 6 1 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6 第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。 算法详解: kruskal+LCA倍增 1.用kruskal求出最小距离sum 2.遍历所有边,将最小生成树中没有的边加入到树中,并去掉形成的环中最大的边(严格) */ #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 2147483647000000 #define MAXM 600005 #define MAXN 100005 int n,m; struct node{ ll u,v,w; bool vis; }path[MAXM]; int cnt,first[MAXN],nxt[MAXM]; ll u[MAXM],v[MAXM],w[MAXM]; void add(int a,int b,int c){ ++cnt,nxt[cnt]=first[a],first[a]=cnt; u[cnt]=a,v[cnt]=b,w[cnt]=c; } ll sum; bool cmp(node a,node b){ if(a.w<b.w)return true; return false; } int f[MAXN]; ll getf(ll x){ if(f[x]==x)return f[x]; return f[x]=getf(f[x]); } void kruskal(){//最小生成树 sum=0; for(int i=0;i<=MAXN;i++)f[i]=i; for(int i=0;i!=MAXM;i++)path[i].vis=false; sort(path+1,path+1+m,cmp); for(ll i=1;i<=m;++i){ ll fa=getf(path[i].u); ll fb=getf(path[i].v); if(fa!=fb){ f[fb]=fa; sum+=path[i].w; path[i].vis=true; } } } ll maxi[MAXN][30],mini[MAXN][30]; int F[MAXN][30],depth[MAXM]; void dfs(ll cur,ll fa,ll d){ F[cur][0]=fa; depth[cur]=d; for(int i=1;i<=20;++i)F[cur][i]=F[F[cur][i-1]][i-1]; for(ll i=first[cur];i;i=nxt[i]){ int to=v[i]; if(to==fa)continue; maxi[v[i]][0]=w[i]; mini[v[i]][0]=-inf; dfs(to,cur,d+1); } } ll LCA(ll x,ll y){ if(depth[x]>depth[y]) swap(x,y); for(ll i=20;i>=0;i--) { if(depth[F[y][i]]>=depth[x]) y=F[y][i]; } if(x==y) return x;//如果x==y表示x与y在同一边 for(int i=20;i>=0;i--) {//up到x与y的父亲相同为止 if(F[x][i]!=F[y][i]) x=F[x][i],y=F[y][i]; } return F[x][0]; } void cal(){ for(ll j=1;j<=20;++j){ for(ll i=1;i<=n;++i){ maxi[i][j]=max(maxi[i][j-1],maxi[F[i][j-1]][j-1]); mini[i][j]=max(mini[i][j-1],mini[F[i][j-1]][j-1]); if(maxi[i][j-1]>maxi[F[i][j-1]][j-1]){ mini[i][j]=max(mini[i][j],maxi[F[i][j-1]][j-1]); } else if(maxi[i][j-1]<maxi[F[i][j-1]][j-1]){ mini[i][j]=max(mini[i][j],maxi[i][j-1]); } } } } ll get_max(ll a,ll b,ll mx){ ll ans = -inf; for(int i=20-1;i>=0;--i){ if(depth[F[a][i]]>=depth[b]){ ll now1 = maxi[a][i]; ll now2 = mini[a][i]; if(now1!=mx) ans = max(ans,now1); else ans = max(ans,now2); a=F[a][i]; } } return ans; } void solve(){ ll ans=inf; for(ll i=1;i<=m;i++){ if(!path[i].vis){ ll a = path[i].u; ll b = path[i].v; ll c = path[i].w; ll lca = LCA(a,b); ll now1 = get_max(a,lca,c); ll now2 = get_max(b,lca,c); ans = min(ans,sum-max(now1,now2)+c); } } printf("%lld\n",ans); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&path[i].u,&path[i].v,&path[i].w); } kruskal(); for(int i=0;i<=m;i++){ if(path[i].vis){ add(path[i].u,path[i].v,path[i].w); add(path[i].v,path[i].u,path[i].w); } } dfs(1,0,1); cal(); solve(); return 0; }
