嚴格次小生成樹
前言
洛谷最優解rank1,u1s1快是真的快，好寫是真的好寫,理解也很好理解
簡直酸爽，舒服了
非原創，僅作解釋
正文
嚴格次小生成樹，顧名思義，權值僅僅小于最小生成樹
重點解釋這個查詢
inline int query(int x,int y,int w)//此時的fa記錄這個點能跳到的最頂端
{
int res=-inf;
x=find(x),y=find(y);//直接跳到頂端，忽略跳過的邊，因為跳過的邊已經用來比較過了
while(x!=y)
{
if(dep[x]<dep[y])swap(x,y);//選取更深的點
if(val[x]<w) res=max(res,val[x]);//尋找x,y之間得最大值
fa[x]=find(father[x]); //父節點連接父節點的父節點
x=find(x);//往父節點跳
}
return res;//回傳值
}
其他的相信帶佬們一定能看懂
完整代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn=1000010;
const int maxm=3000010;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,m;
int w[maxn],cnt=0,val[maxn];
int fa[maxn],sum=0,vis[maxn],dep[maxn],head[maxn];
int father[maxn];//記錄節點的父節點
struct node{
int u,v,w;
}g[maxm];
struct edge{
int v,next,w;
}e[maxn];
inline int read(){
char c;int x=0,f=1;
while(c<'0'|| c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*=f;
}
inline void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline int find(int x){
if(x!=fa[x]) return fa[x]=find(fa[x]);
return x;
}
bool cmp(node a,node b){
return a.w<b.w;
}
inline void kruskal()//求最小生成樹
{
cnt=0;sort(g+1,g+1+m,cmp);
for(register int i=1;i<=m;++i)
{
int u=find(g[i].u),v=find(g[i].v);
if(u!=v)
{
sum+=g[i].w;
fa[u]=v;
vis[i]=1;
if(++cnt==n-1)break;
}
}
}
inline void dfs(int u,int f)//類似于樹剖預處理dfs2
{
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==f)continue;
dep[v]=dep[u]+1;//子節點深度
father[v]=u;//記錄父節點
val[v]=e[i].w;//u到v節點的權值
dfs(v,u);
}
}
inline int query(int x,int y,int w)//此時的fa記錄這個點能跳到的最頂端
{
int res=-inf;
x=find(x),y=find(y);//直接跳到頂端，忽略跳過的邊，因為跳過的邊已經用來比較過了
while(x!=y)
{
if(dep[x]<dep[y])swap(x,y);//選取更深的點
if(val[x]<w) res=max(res,val[x]);//尋找x,y之間得最大值
fa[x]=find(father[x]); //父節點連接父節點的父節點
x=find(x);//往父節點跳
}
return res;//回傳值
}
signed main()
{
n=read(),m=read();//讀入
for(register int i=1;i<=n;++i) fa[i]=i;//初始化并查集
for(register int i=1;i<=m;++i) g[i].u=read(),g[i].v=read(),g[i].w=read();//讀入
kruskal();
for(register int i=1;i<=m;++i)
if(vis[i]){
int u=g[i].u,v=g[i].v,w=g[i].w;
add(u,v,w),add(v,u,w);//建立最小生成樹
}
dep[1]=1;//以1為根，深度為1
dfs(1,0);
int ans=inf;
for(register int i=1;i<=n;++i)fa[i]=i;
for(register int i=1;i<=m;++i)
if(!vis[i]){
int w=g[i].w;
int maxx=query(g[i].u,g[i].v,w);
int num=sum-maxx+w;
if(num!=sum) ans=min(ans,num);//記錄嚴格最小生成樹的值
}
printf("%lld",ans);
return 0;
}
求最小生成樹的時間復雜度\(O(mlogm)\)
預處理和查詢每個邊只會被列舉一次\(O(m)\)
時間復雜度\(O(mlogm)\)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296234.html
標籤：其他
上一篇：貪心演算法