題目描述 小C最近學了很多最小生成樹的演算法，Prim演算法、Kurskal演算法、消圈演算法等等。正當小C洋洋得意之時，小P又來潑小C冷水了。小P說，讓小C求出一個無向圖的次小生成樹，而且這個次小生成樹還得是嚴格次小的，也就是說：如果最小生成樹選擇的邊集是EM，嚴格次小生成樹選擇的邊集是ES，那麼需要滿足 ...
題目描述
小C最近學了很多最小生成樹的演算法，Prim演算法、Kurskal演算法、消圈演算法等等。正當小C洋洋得意之時，小P又來潑小C冷水了。小P說，讓小C求出一個無向圖的次小生成樹，而且這個次小生成樹還得是嚴格次小的，也就是說：如果最小生成樹選擇的邊集是EM，嚴格次小生成樹選擇的邊集是ES，那麼需要滿足：(value(e)表示邊e的權值) \sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)∑e∈EMvalue(e)<∑e∈ESvalue(e)
這下小 C 蒙了，他找到了你，希望你幫他解決這個問題。
輸入輸出格式
輸入格式：
第一行包含兩個整數N 和M，表示無向圖的點數與邊數。 接下來 M行，每行 3個數x y z 表示，點 x 和點y之間有一條邊，邊的權值為z。
輸出格式：
包含一行，僅一個數，表示嚴格次小生成樹的邊權和。(數據保證必定存在嚴格次小生成樹)
輸入輸出樣例
輸入樣例#1： 複製5 6 1 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6輸出樣例#1： 複製
11
說明
數據中無向圖無自環； 50% 的數據N≤2 000 M≤3 000； 80% 的數據N≤50 000 M≤100 000； 100% 的數據N≤100 000 M≤300 000 ，邊權值非負且不超過 10^9 。
裸的次小生成樹
具體怎麼實現一會兒整理一下掛個鏈接吧
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #define int long long using namespace std; const int MAXN=400001; const int INF=1e15+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct Edge { int u,v,w; }E[MAXN]; int Enum=1; void Add(int x,int y,int z) { E[Enum].u=x; E[Enum].v=y; E[Enum].w=z;Enum++; } struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN]; int num=1; int N,M; int fa[MAXN],vis[MAXN],sum; int deep[MAXN],f[MAXN][21],maxx[MAXN][21],minx[MAXN][21]; void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].nxt=head[x]; head[x]=num++; } int find(int x) { if(fa[x]==x) return fa[x]; else return fa[x]=find(fa[x]); } int unionn(int x,int y) { int fx=find(x),fy=find(y); fa[fx]=fy; } int comp(const Edge &a,const Edge &b) { return a.w<b.w; } void Kruskal() { sort(E+1,E+Enum,comp); int tot=0; for(int i=1;i<=Enum-1;i++) { int x=E[i].u,y=E[i].v; if(find(x)!=find(y)) { unionn(x,y),tot++,sum+=E[i].w,vis[i]=1; AddEdge(x,y,E[i].w);AddEdge(y,x,E[i].w); } if(tot==N-1) break; } } void dfs(int now,int fa) { for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==fa) continue; deep[edge[i].v]=deep[edge[i].u]+1; f[edge[i].v][0]=now; maxx[edge[i].v][0]=edge[i].w; dfs(edge[i].v,now); } } void pre() { for(int i=1;i<=18;i++) { for(int j=1;j<=N;j++) { f[j][i]=f[ f[j][i-1] ][i-1]; maxx[j][i]=max(maxx[j][i-1],maxx[ f[j][i-1] ][i-1]); minx[j][i]=max(minx[j][i-1],minx[ f[j][i-1] ][i-1]); if(maxx[j][i-1]>maxx[ f[j][i-1] ][i-1]) minx[j][i]=max(minx[j][i],maxx[ f[j][i-1] ][i-1]); else minx[j][i]=max(minx[j][i],maxx[j][i-1]); } } } int LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); for(int i=18;i>=0;i--) if(deep[ f[x][i] ] >= deep[y] ) x=f[x][i]; if(x==y) return x; for(int i=18;i>=0;i--) if(f[x][i] != f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int findmax(int x,int lca,int val) { int ans=0; for(int i=18;i>=0;i--) { if(deep[ f[x][i] ] >= deep[lca]) { if(maxx[x][i]==val) ans=max(ans,minx[x][i]); else ans=max(ans,maxx[x][i]); x=f[x][i]; } } return ans; } void work() { int ans=INF; for(int i=1;i<=Enum-1;i++) { if(vis[i]) continue; int x=E[i].u,y=E[i].v,z=E[i].w; int lca=LCA(x,y); int lmx=findmax(x,lca,z); int rmx=findmax(y,lca,z); if(max(lmx,rmx)!=z) ans=min(ans,sum+z-max(lmx,rmx)); } printf("%lld",ans); } main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif N=read(),M=read(); memset(head,-1,sizeof(head)); for(int i=1;i<=N;i++) fa[i]=i; for(int i=1;i<=M;i++) { int x=read(),y=read(),z=read(); Add(x,y,z); } Kruskal(); deep[1]=1; dfs(1,0); pre(); work(); return 0; }
