正題

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

---

題目大意

$n$個點$m$條邊的一張無向聯(lián)通圖，每次詢問一個邊集能否同時出現(xiàn)在同一棵最小生成樹上。

$1\le n,m,q,w_i,\sum k\le 5\times 10^5$

---

解題思路

考慮$Kruskal$的做法，每次找一條最小的邊然后判斷是否能夠加入最小生成樹。

考慮到邊權(quán)相同的邊可以任意排序，我們把它稱之為同一層的邊，并且無論任意排序最后產(chǎn)生的圖的連通情況都不會改變。

我們把一個詢問的邊按照邊分層，那么每層的邊都合法這個詢問就合法。

然后對于一個詢問同一層的邊，直接離線，然后把前面的層都加入之后，再把所有這些詢問邊加入判斷是否合法即可。因為前面的層不能重新插，所以做完要撤銷回去。

時間復雜度：$O(n\log n)$（全部同級的話）

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<stack> using namespace std; const int N=5e5+10; struct node{int x,y,w; }e[N],b[N]; int n,m,Q,k,cnt,fa[N],dep[N],mk[N]; bool ans[N]; vector<node> q[N]; vector<int> h[N]; stack<node> cl; int find(int x) {return (fa[x]==x)?x:find(fa[x]);} void unionn(int x,int y){if(dep[x]>dep[y])swap(x,y);cl.push((node){x,y,dep[y]});fa[x]=y;dep[y]=max(dep[y],dep[x]+1);return; } bool cmp(node x,node y) {return x.w<y.w;} int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);scanf("%d",&Q);for(int i=1;i<=Q;i++){int k;scanf("%d",&k);for(int j=1,x;j<=k;j++)scanf("%d",&x),b[j]=e[x];sort(b+1,b+1+k,cmp);ans[i]=1;for(int j=1;j<=k;j++){if(b[j].w!=b[j-1].w)++cnt,h[b[j].w].push_back(cnt),mk[cnt]=i;q[cnt].push_back(b[j]);}}sort(e+1,e+1+m,cmp);for(int i=1;i<=n;i++)fa[i]=i;for(int l=1,r=1;l<=m;l=r+1){while(e[r+1].w==e[l].w)r++;int w=e[l].w;while(!cl.empty())cl.pop();for(int j=0;j<h[w].size();j++){int p=h[w][j];for(int i=0;i<q[p].size();i++){int x=q[p][i].x,y=q[p][i].y;x=find(x);y=find(y);if(x==y){ans[mk[p]]=0;break;}unionn(x,y);}while(!cl.empty()){node x=cl.top();cl.pop();dep[x.y]=x.w;fa[x.x]=x.x;}}for(int i=l;i<=r;i++){int x=find(e[i].x),y=find(e[i].y);if(x==y)continue;unionn(x,y);}}for(int i=1;i<=Q;i++)if(ans[i])puts("YES");else puts("NO");return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF891C-Envy【可撤销并查集】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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