https://vjudge.net/problem/UVA-10600/origin
板子题。
求非严格次小生成树树有大致有两种。一种是暴力，枚举不在最小生成树的边，然后跑n-1次最小生成树。(O(n^2logn)大致)
或者dfs找最小生成树环上的最长边替换掉。
借xayata_大佬的图。
优化的办法就是在最小生成树中，看成一颗树，然后化成有根树，用倍增的思路融合ST的思路，维护u,v的lca(u,v)的最长边。
一个倍增数组记录父亲，一个倍增数组记录(u,lca(u,v))之间的最长边。
然后枚举。大致是O(nlogn)
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=150; typedef int LL; LL n,m; struct P{ LL u,v,c; LL num; }edge[maxn*maxn]; vector<P>g[maxn]; LL p[maxn]; LL bz[maxn][20],maxi[maxn][20],deep[maxn]; bool used[maxn*maxn],vis[maxn*maxn]; bool cmp(P A,P B) { return A.c<B.c; } LL find(LL x) { if(p[x]==x) return p[x]; return p[x]=find(p[x]); } void init() { for(LL i=1;i<110;i++) p[i]=i,g[i].clear(); memset(vis,0,sizeof(vis)); memset(used,0,sizeof(used)); memset(deep,0,sizeof(deep)); memset(edge,0,sizeof(edge)); memset(bz,0,sizeof(bz)); memset(maxi,0,sizeof(maxi)); } void dfs(LL u,LL fa) { bz[u][0]=fa;///cout<<"fuck"<<endl; for(LL i=0;i<g[u].size();i++){ LL v=g[u][i].v; if(v==fa||vis[v]) continue; vis[v]=true; deep[v]=deep[u]+1; maxi[v][0]=edge[g[u][i].num].c; dfs(v,u); } } void cal() { for(LL i=1;i<=18;i++) { for(LL j=1;j<=n;j++) { bz[j][i]=bz[bz[j][i-1]][i-1]; maxi[j][i]=max(maxi[j][i-1],maxi[bz[j][i-1]][i-1]); } } } LL LCA(LL x,LL y) { if(deep[x]<deep[y]) swap(x,y); for(LL i=18;i>=0;i--){ if(deep[bz[x][i]]>=deep[y]) x=bz[x][i]; } if(x==y) return x; for(LL i=18;i>=0;i--){ if(bz[x][i]!=bz[y][i]){ x=bz[x][i];y=bz[y][i]; } } return bz[x][0]; } LL qmax(LL u,LL v,LL maxx) { LL res=-0x3f3f3f3f; for(LL i=18;i>=0;i--) { if(deep[bz[u][i]]>=deep[v]) { res=max(res,maxi[u][i]); u=bz[u][i]; } } return res; } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); LL t;cin>>t; while(t--) { init(); cin>>n>>m; for(LL i=1;i<=m;i++){ LL u,v,c;cin>>u>>v>>c; edge[i].u=u;edge[i].v=v;edge[i].c=c; } sort(edge+1,edge+1+m,cmp); LL ans=0;//最小生成树 for(LL i=1;i<=m;i++) { LL u=edge[i].u;LL v=edge[i].v;LL c=edge[i].c; if(find(u)==find(v)) continue; p[find(u)]=find(v); /// cout<<edge[i].u<<"---"<<edge[i].v<<endl; g[u].push_back({u,v,c,i}); g[v].push_back({v,u,c,i}); used[i]=true; ans+=edge[i].c; } deep[1]=1;vis[1]=true; dfs(1,-1); cal(); LL ans2=0x3f3f3f3f; for(LL i=1;i<=m;i++) { if(used[i]) continue; LL u=edge[i].u; LL v=edge[i].v; LL c=edge[i].c; LL lca=LCA(u,v); LL maxu=qmax(u,lca,c); LL maxv=qmax(v,lca,c); ans2=min(ans2,ans-max(maxu,maxv)+c); } cout<<ans<<" "<<ans2<<endl; } return 0; }
