- 给定一张\(n\)个点\(m\)条边的无向图。
- \(q\)次询问,每次给出\(a\)个二元组\((x_i,y_i)\),询问至少与其中一个\(x_i\)距离不超过\(y_i\)的点数。
- \(n\le10^3,m,q\le10^5,\sum a\le2.1\times10^6\)
前言:威廉是仙人掌啊
\(bitset\)处理询问
显然对于一次询问,我们只要对每个\(x_i\)分别求出满足条件的点集,再给它们取个并集就可以了,具体实现可以使用\(bitset\)。
因此,只要对每个\(x_i\)求出它到所有点的距离,再把所有点和所有与它相关的二元组分别按距离排序,再只要双指针扫一遍同时维护好\(bitset\)即可。
\(Floyd\)高光时刻
如何求出一个点到所有点的距离?
一个看起来复杂度无比正确的算法,就是从每个点出发跑一遍\(BFS\),复杂度\(O(nm)\)。然而可能是因为我人傻常数大,终究还是\(T\)掉了。
这时候,我就想起一个常数极小的算法——\(Floyd\)!
即便它的复杂度\(O(n^3)\)理论上极不可能通过此题,但它优秀的常数让它在实测中跑得飞快。。。
P.S. 其实后来看了题解发现我根本没利用边权为\(1\)的性质,但反过来我这做法应该能做边权不为\(1\)的版本,尽管复杂度有点诡异。
代码:\(O(n^3+\frac{n\sum a}{32})\)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
#define M 100000
using namespace std;
int n,m,Qt,f[N+5][N+5];struct Q
{
int p,d;I Q(CI x=0,CI y=0):p(x),d(y){}I bool operator < (Con Q& o) Con {return d<o.d;}
};vector<Q> q[N+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int p;I bool cmp(CI x,CI y) {return f[p][x]<f[p][y];}//按照到p的距离排序
int id[N+5];bitset<N+5> S,ans[M+5];I void Solve()
{
S.reset(),sort(id+1,id+n+1,cmp),sort(q[p].begin(),q[p].end());vector<Q>::iterator it=q[p].begin();
for(RI i=1;i<=n&&it!=q[p].end()&&f[p][id[i]]<1e9;S.set(id[i++]))//距离达到INF时直接结束循环
if(f[p][id[i]]^f[p][id[i-1]]) W(it!=q[p].end()&&it->d==f[p][id[i-1]]) ans[it->p]|=S,++it;//维护双指针
W(it!=q[p].end()) ans[it->p]|=S,++it;//处理没处理完的询问
}
int main()
{
RI i,j,k,x,y;for(read(n,m,Qt),i=1;i<=n;++i) for(j=1;j<=n;++j) f[i][j]=i^j?1e9:0;
for(i=1;i<=m;++i) read(x,y),x^y&&(f[x][y]=f[y][x]=1);//注意自环
for(k=1;k<=n;++k) for(id[k]=k,i【洛谷6328】我是仙人掌(Floyd+bitset)=1;i<=n;++i) for(j=1;j<=n;++j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//Floyd
for(i=1;i<=Qt;++i) for(read(k);k;--k) read(x,y),q[x].push_back(Q(i,y));//询问扔到对应点的vector中
for(i=1;i<=n;++i) p=i,Solve();for(i=1;i<=Qt;++i) writeln(ans[i].count());return clear(),0;//对每个点分别求解,然后输出每个询问的并集大小
}