JZOJ 5932. 【NOIP2018模拟10.27】情报中心
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
-
这题暴力的话是 ,就是预处理出两点距离,然后枚举点看其能否被到达。
-
但是这样显然不能通过此题。
-
考虑使用STL的 来优化并解决此题。
-
设 ,表示从点 出发,走不超过 的距离能到达的点的集合。
-
这样设的空间复杂度是 的,不会爆空间(卡得还真紧……)。
-
于是我们预处理 ,比如到一个点 走距离 恰好走到 ,则 。
-
最后对 做一遍前缀或运算即可,即:
-
那么回答询问就容易啦!将每个 或起来,输出 集合中 的个数就好了。
-
然而这题还要卡常,如果用前向星等链表、vector存储边的话还会 。
-
为了寻址复杂度更优,我们可以用邻接表来存边。。
-
注意还要用一个邻接矩阵来判断重边,不然还会爆邻接表数组。。(自环当然也要判)
-
时空复杂度 。
Code
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cctype>
using namespace std;
const int N=1005;
int a[N][N],dis[N],que[N],mx[N];
bool bz[N][N];
bitset<N>f[N][N],ans;
inline int read()
{
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();
return w?-X:X;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int min(int x,int y)
{
return x<y?x:y;
}
int main()
{
freopen("center.in","r",stdin);
freopen("center.out","w",stdout);
int n=read(),m=read(),q=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
if(x==y || bz[x][y]) continue;
a[x][++a[x][0]]=y;
a[y][++a[y][0]]=x;
bz[x][y]=bz[y][x]=true;
}
for(int i=1;i<=n;i++)
{
memset(dis,60,sizeof(dis));
dis[que[1]=i]=0;
f[i][0][i]=1;
int l=0,r=1;
while(l<r)
{
int x=que[++l];
for(int j=1;j<=a[x][0];j++)
{
int y=a[x][j];
if(dis[x]+1<dis[y])
{
f[i][dis[y]=dis[x]+1][y]=1;
que[++r]=y;
}
}
}
int up=mx[i]=dis[que[r]];
for(int j=1;j<=up;j++) f[i][j]|=f[i][j-1];
}
while(q--)
{
ans.reset();
int k=read();
while(k--)
{
int x=read(),d=min(mx[x],read());
ans|=f[x][d];
}
write(ans.count()),putchar('\n');
}
return 0;
}