[AGC002D] Stamp Rally 整体二分+并查集

2024-03-03 15:23:40

Description

给你一个n个点m个条边构成的简单无向连通图，有Q组询问，每次询问从两个点x,y走出两条路径，使这两条路径覆盖z个点，求得一种方案使得路径上经过的变的最大编号最小。

Input

第一行两个整数n,m，如题目所述

接下来m行，每行两个整数x,y描述一条边

接下来一个整数Q，如题目所述

接下来Q行，每行三个整数x,y,z，如题目描述

Output

Q行，每行一个正整数，如题目描述

Sample Input

Sample Output

HINT

n,m,q≤10^5

Sol

考虑单组询问的做法，显然可以二分答案，然后用并查集把所有小于等于的边合并，判断是否可行即可。

这里每组询问互相独立，我们上整体二分即可。

如果把整体二分写成BFS形式的话不用还原并查集啦，而且好写得多，具体地，我们建出类似线段树的东西，然后求出每个线段的mid，按照顺序并查集合并，如果当前i和这一层其中一个mid相等就判断这个节点vector中的元素是否达标并下传即可。

每一层要清空并查集。

Code

#include <bits/stdc++.h>

using namespace std;

struct que{int x,y,z;}q[100005];vector<int>v[800050];

int n,m,Q,x,y,now=1,U[100005],V[100005],cnt[100005],ans[100005],mid[800050],l[800050],r[800050],f[100005],sz[100005];

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

void bud(int x,int L,int R){l[x]=L;r[x]=R;mid[x]=(L+R)>>1;if(L==R) return;bud(x*2,L,mid[x]);bud(x*2+1,mid[x]+1,R);}

int main()

{

    scanf("%d%d",&n,&m);memset(ans,0x3f,sizeof(ans));

    for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),U[i]=x,V[i]=y;

    scanf("%d",&Q);bud(1,1,m);

    for(int i=1;i<=Q;i++) scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z),v[1].push_back(i);

    for(int gg=m*4;gg;gg>>=1)

    {

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

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

        {

            if((x=find(V[i]))!=(y=find(U[i]))) f[y]=f[x],sz[x]+=sz[y];

            if(i==mid[now]) for(int j=0;j<v[now].size();j++)

            {

                int a=find(q[v[now][j]].x),b=find(q[v[now][j]].y);

                cnt[v[now][j]]=(a==b)?sz[a]:sz[a]+sz[b];

                if(cnt[v[now][j]]<q[v[now][j]].z) v[now*2+1].push_back(v[now][j]);

                else v[now*2].push_back(v[now][j]),ans[v[now][j]]=mid[now];

            }

            if(i==mid[now]||!mid[now]) now++;

        }

    }

    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);

}

码农公寓