[DS记录]AT1998 [AGC002D] Stamp Rally
command_block
2021-02-28 21:18:25
**题意** : 给出一张 $n$ 个点 $m$ 条边的无向连通图。
$q$ 次询问从两个点 $x,y$ 出发，希望经过的点(不重复)数量等于 $z$ ，经过的边最大编号最小是多少。
$n,m,q\leq 10^5$ ，时限$\texttt{2s}$。
------------
考虑整体二分。BFS + 并查集即可做到 $O\big(n\alpha(n)\log n\big)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
int f[MaxN],c[MaxN];
void Init(int n)
{for (int i=1;i<=n;i++)c[f[i]=i]=1;}
int find(int u)
{return f[u]==u ? u : f[u]=find(f[u]);}
void merge(int u,int v){
u=find(u);v=find(v);
if (u==v)return ;
if (c[u]>c[v])swap(u,v);
c[f[u]=v]+=c[u];
}
struct Line{int u,v;}l[MaxN];
struct QData{int u,v,c,ans;}b[MaxN];
struct MData{int l,r,tl,tr;}t[MaxN<<1];
int tim,ql,qr;
void ltg(int lim){
for (;tim<=lim;++tim)
merge(l[tim].u,l[tim].v);
}
int calc(int u,int v){
u=find(u);v=find(v);
return u==v ? c[u] : c[u]+c[v];
}
int p[MaxN],sp[MaxN];
void solve(int l,int r,int tl,int tr)
{
if (tl==tr){
for (int i=l;i<=r;i++)b[p[i]].ans=tl;
return ;
}int tmid=(tl+tr)>>1,mid=l-1,tn=0;
ltg(tmid);
for (int k=l;k<=r;k++){
int i=p[k];
if (calc(b[i].u,b[i].v)>=b[i].c)p[++mid]=i;
else sp[++tn]=i;
}
for (int i=1;i<=tn;i++)p[i+mid]=sp[i];
if (l<=mid)t[++qr]=(MData){l,mid,tl,tmid};
if (mid<r)t[++qr]=(MData){mid+1,r,tmid+1,tr};
}
int n,m,q;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&l[i].u,&l[i].v);
scanf("%d",&q);
for (int i=1;i<=q;i++)
scanf("%d%d%d",&b[p[i]=i].u,&b[i].v,&b[i].c);
t[ql=qr=1]=(MData){1,q,1,m};
while(ql<=qr){
int sav=qr;
Init(n);tim=1;
for (int i=ql;i<=sav;i++)
solve(t[i].l,t[i].r,t[i].tl,t[i].tr);
ql=sav+1;
}
for (int i=1;i<=q;i++)
printf("%d\n",b[i].ans);
return 0;
}
```