JZOJ-senior-5932. 【NOIP2018模拟10.27】情报中心

Time Limits: 1500 ms Memory Limits: 262144 KB

Description

飞纷火战来年近国 D 和国 C
飞乱子鸽来年近国 D 和国 C

最近，C 国成功地渗透进入了 D 国的一个城市。这个城市可以抽象成一张有 n 个节点，节点之间有 m 条双向道路连接的无向图，每条道路的⻓度都为 1 。
经过侦查，C 国情报部部⻓ GGB 惊讶地发现，这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这个城市内设立情报机构。情报专家 TAC 在侦查后，安排了 q 种设立情报机构的方案。这些方案中，第 i 种方案将计划建立 ki 个情报机构，第 j 个情报机构可以安排人员到距离其不超过 di,j 的节点上收集情报。

Input

从文件 center.in 中读入数据。

输入第一行包含三个正整数 n, m, q ，分别表示城市的节点个数、道路条数和方案个数。

接下去 m 行每行两个正整数 u, v ，表示存在一条连接城市 u 和城市 v 的双向道路。

接下去 q 行，每行表示一个方案。第一个正整数 k 表示该种方案将计划建立 k 个情报机构，之后是 2k 个正整数，其中第 2i − 1 个数表示方案中第 i 个情报机构所在的节点编号，第 2i 个数表示第 i 个情报点所能派出情报人员的最远距离。

Output

输出到文件 center.out 中。

输出包含 q 行，每行包含一个整数，表示相应询问的答案。

Sample Input

5 8 3
1 2
1 3
1 4
1 5
2 4
2 5
3 5
4 5
1 2 1
1 1 1
2 2 2 3 1

样例 2
见选手目录下的 center/center2.in 与 center/center2.ans 。

Sample Output

4
5
5

Data Constraint

题目更正：di,j值域在int范围内；q小于等于100000

Solution

• 第一次用bitset这个自带1/32常数的黑科技
• bitset可以理解为一个每位只能是 $0$0 或 $1$1 的数组，但是因为它经过压位，时空复杂度都是 $n/32$n/32 ，其中n是数组位数
• 开一个bitset类型的 $f$f ，其中 $f_{i,j}$fi,j​ 表示从 $i$i 开始走， $j$j 步以内能到达哪些点，<= $j$j 步不好求那就先求= $j$j 步的，然后前缀和 $or$or 一下就好了
• $bfs$bfs 时间复杂度为 $O(n(n+m))$O(n(n+m)) ，总询问时间复杂度为 $O(\frac{n\sum{k}}{32})$O(32n∑k​)
• 如果你有梦想，nk做法的寻址优化版貌似也能过

Code

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define P(c) putchar(c)

using namespace std;

const int N=1010;
int n,m,q,x,y,k;
int d[N],dis[N],a[N][N],b[N][N];
bitset<N> ans,f[N][N];

inline void read(int &n)
{
	int x=0,w=0; char ch=0;
	while(!isdigit(ch)) w|=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	n=w?-x:x;
}

inline void write(int x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

void bfs(int s)
{
	memset(dis,127,sizeof(dis));
	int l=0,r=1; d[1]=s,dis[s]=0;
	while(l<r)
	{
		x=d[++l],y=dis[x];
		fo(i,1,b[x][0])
			if(dis[b[x][i]]>n)
				dis[b[x][i]]=y+1,d[++r]=b[x][i];
	}
	fo(i,1,n) if(dis[i]<n) f[s][dis[i]][i]=1;
	fo(i,1,n) f[s][i]|=f[s][i-1];
}

int main()
{
	freopen("center.in","r",stdin);
	freopen("center.out","w",stdout);
	read(n),read(m),read(q);
	fo(i,1,m) read(x),read(y),a[x][y]=a[y][x]=1;
	fo(i,1,n)
		fo(j,1,n)
			if(a[i][j]) b[i][++b[i][0]]=j;
	fo(i,1,n) bfs(i);
	while(q--)
	{
		read(k),ans.reset();
		fo(i,1,k) read(x),read(y),ans|=f[x][y];
		write(ans.count()),P('\n');
	}
}