正題

題目鏈接:https://www.luogu.com.cn/problem/P5631

---

題目大意

$n$個(gè)點(diǎn)$m$條邊的一張圖，求$mex$值最小的一棵生成樹(shù)。

---

解題思路

考慮比較暴力的做法，枚舉答案，然后判斷其他邊能否構(gòu)成一棵生成樹(shù)。

發(fā)現(xiàn)一條邊會(huì)被重復(fù)加入多次，可以考慮不刪除其他不動(dòng)的邊。

具體方法在線段樹(shù)上，對(duì)于邊權(quán)為$w$的邊，每次把$w$丟到$[1,w?1]\cup [w+1,\infty ]$這個(gè)區(qū)間。

然后在線段樹(shù)上往下走，維護(hù)一個(gè)不壓縮路徑但是按秩合并的可撤銷(xiāo)堆，每次走到一個(gè)節(jié)點(diǎn)就把這個(gè)節(jié)點(diǎn)上的邊加入，離開(kāi)的時(shí)候就撤銷(xiāo)掉。這樣到葉節(jié)點(diǎn)時(shí)判斷是否是一棵生成樹(shù)就好了。

時(shí)間復(fù)雜度$O(n\log n\log w)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cctype> using namespace std; const int N=1e6+10,L=1e5+2; struct line{int x,y; }cl[N]; int n,m,cnt,fa[N],siz[N]; vector<line> v[N<<1]; int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int find(int x) {return (fa[x]==x)?x:find(fa[x]);} void unionm(int x,int y){x=find(x);y=find(y);if(x==y)return;if(siz[x]<siz[y])swap(x,y);cl[++cnt]=(line){x,y};siz[x]+=siz[y];fa[y]=x;return; } void clear_to(int w){while(cnt>w){int x=cl[cnt].x,y=cl[cnt].y;siz[x]-=siz[y];fa[y]=y;cnt--;}return; } void Change(int x,int L,int R,int l,int r,line w){if(L==l&&R==r){v[x].push_back(w);return;}int mid=(L+R)>>1;if(r<=mid)Change(x*2,L,mid,l,r,w);else if(l>mid)Change(x*2+1,mid+1,R,l,r,w);else Change(x*2,L,mid,l,mid,w),Change(x*2+1,mid+1,R,mid+1,r,w);return; } int Solve(int x,int l,int r){int top=cnt;for(int i=0;i<v[x].size();i++)unionm(v[x][i].x,v[x][i].y);if(l==r){if(cnt==n-1)return l;clear_to(top);return 0;}int mid=(l+r)>>1,k;if(k=Solve(x*2,l,mid))return k;if(k=Solve(x*2+1,mid+1,r))return k;clear_to(top);return 0; } int main() {n=read();m=read();for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;for(int i=1;i<=m;i++){int x=read(),y=read(),w=read()+1;if(w!=1)Change(1,1,L,1,w-1,(line){x,y});if(w!=L)Change(1,1,L,w+1,L,(line){x,y});}printf("%d\n",Solve(1,1,L)-1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5631-最小mex生成树【线段树,并查集】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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