一、總體思路

首先,我這一題的思路是倍增LCA+Kruskal

?

首先，kruskal求最小生成樹? 不會的戳這里

求次小生成樹 倍增? LCA

關(guān)鍵在于次小生成樹怎么求：

問自己一些問題

怎么求不嚴(yán)格次小生成樹

不嚴(yán)格次小生成樹為什么不嚴(yán)格

方法每次選擇U—V之間的邊，前提是最小生成樹上不存在的邊，添邊之后刪去較短邊，使用LCA找到祖先，刪邊，這里保證次小生成樹的是？只要添得邊不是U-V在樹上最小距離即可。

模板

#include<iostream> #include<algorithm> #include<vector> #include<cstdio> typedef long long ll; using namespace std; const int M=1e5+100; ll n,m,res,ans=0x3f3f3f3f,mx; int f[M],fa[25][M],dep[M]; ll d[2][25][M]; bool used[3*M],vis[M]; vector<int> a[M]; struct Edge{int from, to;ll val;bool operator < (const Edge y){return val < y.val;} }e[3*M]; int F(int x){if(f[x]==x) return x;return f[x]=F(f[x]); } void kruskal(){ //kruskal 算最大生成樹（已保證任意兩點之間最小限重最優(yōu)）sort(e,e+m); int lef=n-1;for(int i=1;i<=n;++i) f[i]=i;for(int i=0;i<m && lef;++i){int x=F(e[i].from),y=F(e[i].to);if(x!=y){f[x]=y; res+=e[i].val;used[i]=1; --lef;mx=max(mx , e[i].val);} } } void dfs(int x){ //深搜建樹（可能不止一棵，因為數(shù)據(jù)未保證是連通圖） vis[x]=true;for(int i=1;i<=23;++i){fa[i][x]=fa[i-1][fa[i-1][x]];ll t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];d[0][i][x]=max(t1 , t2);d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));}for(int i=0;i<a[x].size();++i){int t=e[a[x][i]].to+e[a[x][i]].from-x;if(vis[t]) continue; //vis為1表示是父節(jié)點 dep[t]=dep[x]+1; fa[0][t]=x;d[0][0][t]=e[a[x][i]].val; dfs(t);} } int lca(int u,int v){if(dep[u]<dep[v])swap(u,v);if(dep[u]!=dep[v]){ //將深度做相等for(int i=23,h=dep[u]-dep[v];i>=0;--i)if(h&(1<<i)) u=fa[i][u];}if(u==v) return u; //如果已經(jīng)在一個節(jié)點上就直接返回 for(int i=23;i>=0;--i) if(fa[i][u]!=fa[i][v])u=fa[i][u] , v=fa[i][v];return fa[0][u]; } ll get(int u,int v,int c){int fht=lca(u,v);ll m1=0,m2=0;for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht];i>=0;--i){if(h1&(1<<i)){if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];else if(d[0][i][u]>m2) m2=d[0][i][u];else m2=max(m2 , d[1][i][u]);} if(h2&(1<<i)){if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];else if(d[0][i][v]>m2) m2=d[0][i][v];else m2=max(m2 , d[1][i][v]);}} if(m1==c) return c-m2;else return c-m1; } int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;++i){int u,v; ll w;scanf("%d%d%lld",&u,&v,&w);e[i].from=u;e[i].to=v;e[i].val=w;} kruskal();for(int i=0;i<m;++i) if(used[i]){a[e[i].from].push_back(i);a[e[i].to].push_back(i);} dep[1]=1; dfs(1);for(int i=0;i<m;++i) if(!used[i]){if(e[i].val-mx>ans) break;ll t=get(e[i].from , e[i].to , e[i].val);ans=min(ans , t);} return printf("%lld\n",res+ans),0;

?

總結(jié)

以上是生活随笔為你收集整理的疯子的算法总结11--次小生成树+严格次小生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。