codeforces 892E（离散化+可撤销并查集）

题意

　　给出一个n个点m条边的无向联通图(n,m<=5e5)，有q(q<=5e5)个询问

　　每个询问询问一个边集{Ei}，回答这些边能否在同一个最小生成树中

分析

　　要知道一个性质，就是权值不同的边之间是独立的，即权值为x的所有边的选取不影响权值>x的边的选取

　　于是我们可以把所有询问离线，按边权排序，对于当前处理的边权，如果有某个询问在其中，那么我们把这些边加进去看有没有环，如果有，那么这个询问就被叉掉了，当然处理完了还要把刚才的操作撤销掉

　　处理了当前权值x的所有询问，最后别忘了把权值为x的边做kruskal算法加进去

　　这样时间复杂度是带log的（按秩合并的可撤销并查集的复杂度）

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=5e5;

 int f[maxn+],sz[maxn+];

 int ans[maxn+];

 struct Edge

 {

     int u,v,w;

 }edge[maxn+];

 vector<int> b[maxn+];

 vector<int> q[maxn+];

 struct question

 {

     int id,from,to;

 };

 vector<question> a[maxn+];

 int n,m,Q;

 bool cmp(const int x,const int y)

 {

     return edge[x].w<edge[y].w;

 }

 stack<pair<int,int> > s;

 int find(int x)

 {

     if(f[x]==x) return x;else return find(f[x]);

 }

 void Union(int x,int y)

 {

     if(sz[x]<sz[y]) f[x]=y,sz[y]+=sz[x],s.push(make_pair(x,y));

     else f[y]=x,sz[x]+=sz[y],s.push(make_pair(y,x));

 }

 void remove()

 {

     pair<int,int> u=s.top();

     s.pop();

     f[u.first]=u.first;

     sz[u.second]-=sz[u.first];

 }

 bool check(int id,int from,int to)

 {

     bool ans=;

     int sum=;

     for(int i=from;i<=to;++i)

     {

         int p=q[id][i];

         int x=find(edge[p].u),y=find(edge[p].v);

         if(x!=y) Union(x,y),++sum;else ans=;

     }

     for(int i=;i<=sum;++i) remove();

     return ans;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;++i)

         scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w),b[edge[i].w].push_back(i);

     scanf("%d",&Q);

     for(int i=;i<=Q;++i)

     {

         q[i].clear();

         int num,x;

         scanf("%d",&num);

         while(num--)

         {

             scanf("%d",&x);

             q[i].push_back(x);

         }

         sort(q[i].begin(),q[i].end(),cmp);

         int from=;

         for(int j=;j<q[i].size();++j)

             if(edge[q[i][j]].w!=edge[q[i][j-]].w)

             {

                 a[edge[q[i][j-]].w].push_back({i,from,j-});

                 from=j;

             }

         a[edge[q[i][q[i].size()-]].w].push_back({i,from,q[i].size()-});

     }

     for(int i=;i<=n;++i) f[i]=i,sz[i]=;

     for(int i=;i<=maxn;++i)

     {

         for(int j=;j<a[i].size();++j)

             if(!check(a[i][j].id,a[i][j].from,a[i][j].to)) ans[a[i][j].id]=;

         for(int j=;j<b[i].size();++j)

             {

                 int p=b[i][j];

                 int x=find(edge[p].u),y=find(edge[p].v);

                 if(x!=y) Union(x,y);

             }

     }

     for(int i=;i<=Q;++i)

         if(ans[i]) printf("NO\n");else printf("YES\n");

     return ;

 }

巴特西

codeforces 892E（离散化+可撤销并查集）

最新文章

热门文章