正題

P4180

---

題目大意

求嚴格次小生成樹

---

解題思路

一定存在一種嚴格次小生成樹，和最小生成樹只差一條邊，不然可以用一條最小生成樹上的邊代替，從而使邊權和更小

那么可以先構造出最小生成樹，然后枚舉每一條不在最小生成樹中的邊，然后求最小生成樹中路徑上的最大值和嚴格次大值（因為可能相等，所以要求嚴格次大值），最后計算最小的替換代價

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100100 using namespace std; ll n,m,x,y,mx1,mx2,ans,tot,num; ll h[N],fa[N],dep[N],f[N][20],g[N][20][2]; struct rec {ll to,nx,l; }e[N<<1]; struct line {ll x,y,z,p; }l[N*3]; void add(ll x,ll y,ll z) {e[++tot].to=y;e[tot].l=z;e[tot].nx=h[x];h[x]=tot;return; } bool cmp(line a,line b) {return a.z<b.z; } ll find(ll x) {return (fa[x]==x?x:fa[x]=find(fa[x])); } void get(ll &mx,ll &pmx,ll x) {if(x>mx)pmx=mx,mx=x;else if(pmx<x&&x<mx)pmx=x;return; } void dfs(ll x) {for(ll i=1;i<=16;++i){f[x][i]=f[f[x][i-1]][i-1];get(g[x][i][1],g[x][i][0],g[x][i-1][1]);get(g[x][i][1],g[x][i][0],g[x][i-1][0]);get(g[x][i][1],g[x][i][0],g[f[x][i-1]][i-1][1]);get(g[x][i][1],g[x][i][0],g[f[x][i-1]][i-1][0]);}for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;if(y==f[x][0])continue;dep[y]=dep[x]+1;f[y][0]=x;g[y][0][1]=e[i].l;dfs(y);}return; } void lca(ll &mx1,ll &mx2,ll x,ll y) {if(dep[x]<dep[y])swap(x,y);for(ll i=16;i>=0;--i)if(dep[f[x][i]]>=dep[y]){get(mx1,mx2,g[x][i][1]);get(mx1,mx2,g[x][i][0]);x=f[x][i];}for(ll i=16;i>=0;--i)if(f[x][i]!=f[y][i]){get(mx1,mx2,g[x][i][1]);get(mx1,mx2,g[x][i][0]);get(mx1,mx2,g[y][i][1]);get(mx1,mx2,g[y][i][0]);x=f[x][i];y=f[y][i];}if(x!=y){get(mx1,mx2,g[x][0][1]);get(mx1,mx2,g[x][0][0]);get(mx1,mx2,g[y][0][1]);get(mx1,mx2,g[y][0][0]);}return; } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;++i)scanf("%lld%lld%lld",&l[i].x,&l[i].y,&l[i].z);sort(l+1,l+1+m,cmp);for(ll i=1;i<=n;++i)fa[i]=i;for(ll i=1;i<=m;++i){x=find(l[i].x);y=find(l[i].y);if(x==y)continue;add(l[i].x,l[i].y,l[i].z);add(l[i].y,l[i].x,l[i].z);num+=l[i].z;fa[x]=y;l[i].p=1;}memset(g,-1,sizeof(g));f[1][0]=1;dep[1]=1;dfs(1);ans=1e15;for(ll i=1;i<=m;++i)if(!l[i].p){mx1=mx2=-1;lca(mx1,mx2,l[i].x,l[i].y);if(mx1>=0&&mx1<l[i].z)ans=min(ans,num-mx1+l[i].z);if(mx2>=0&&mx2<l[i].z)ans=min(ans,num-mx2+l[i].z);}printf("%lld",ans);return 0; }

總結

以上是生活随笔為你收集整理的【kruskal】【倍增】严格次小生成树（P4180）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。