Codeforces Round #446 (Div. 2) E. Envy （并查集）

本文主要是介绍Codeforces Round #446 (Div. 2) E. Envy （并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

思路：

     根据题目分析出这样结论：最小生成树各个值形成的森林是确定的，所以各个值之间互相独立，那么我们就可以对于某个值进行这样的分析，将边权值小于这个值的边都加进去，然后开始讨论这个值，如果发现这个值里面某个边所连接的两边属于同一集合，那么这个边是不可行的
     那么现在还需要讨论一种问题，就是虽然两个边单独说的话都可行，但他们放一起就不可行了，这个时候，我们只需要对每个集合单独讨论即可
     好了，现在只剩下最后一个问题了，怎么维护每个集合的过程，毕竟一个集合结束后，我们就需要将并查积恢复到以前的过程，其实只要在find的过程中暴力维护哪些改变了即可

错误及反思：

之前在更新的时候，一种是某个价值挨个遍历，另一种是先把问题放一起后，统一对某个价值进行遍历。
然而，后一种写法会T，具体分析就是因为对于并查集中元素的修改数量，一个是 $\sum_{i=1}^{n} {\log_2{k_i}}$ 另一个是 ${\log_2{\sum_{i=1}^{n}{k_i}}}$

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int n,m,q;
struct NODE{int u,v,val;
}node[N],onode[N];bool cmp(NODE x,NODE y){return x.val<y.val;
}
struct Q{ int x,id; };
bool cmp2(Q x,Q y){if(onode[x.x].val==onode[y.x].val)return x.id<y.id;return onode[x.x].val<onode[y.x].val;
}
vector<Q> v;
vector<int> bd;
int fa[N],now[N],sz[N],did[N],prefa[N];
int getfa(int x){if(fa[x]!=x) bd.push_back(x);return fa[x]=fa[x]==x?x:getfa(fa[x]);
}
int getfa2(int x){return fa[x]=fa[x]==x?x:getfa2(fa[x]);
}int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].val);onode[i]=node[i];}sort(node,node+m,cmp);for(int i=1;i<=n;i++){ fa[i]=i;prefa[i]=i;}scanf("%d",&q);int tot=0;for(int i=0,tt;i<q;i++){scanf("%d",&tt);for(int j=0,ta;j<tt;j++){scanf("%d",&ta);Q tb={ta-1,i};v.push_back(tb);tot++;}}sort(v.begin(),v.end(),cmp2);int j=0;for(int i=0;i<m;i++){int val=node[i].val;for(;j<tot;j++){bd.clear();if(onode[v[j].x].val!=val) break;if(did[v[j].id]) continue;int need=v[j].id;while(j<tot&&onode[v[j].x].val==val&&v[j].id==need){int u=onode[v[j].x].u,V=onode[v[j].x].v;int fa1=getfa(u),fa2=getfa(V);if(fa1==fa2){did[v[j].id]=true;}else{bd.push_back(fa1);fa[fa1]=fa2;}j++;}j--;for(int k=0;k<bd.size();k++)fa[bd[k]]=prefa[bd[k]];}while(node[i].val==val&&i<m){int u=node[i].u,V=node[i].v;int fa1=getfa2(u),fa2=getfa2(V);if(fa1!=fa2) fa[fa1]=fa2;prefa[fa1]=fa2;i++;}i--;}for(int i=0;i<q;i++)if(did[i]) printf("NO\n");else printf("YES\n");
}