[Ynoi2015]我回来了

题目大意：

给定一张无向无权图，每次给定若干个二元组\((x_i,y_i)\)，定义点\(u\)满足条件，当且仅当存在\(i\)，并满足\(dist(u,x_i)\leqslant y_i\)（\(dist(u,v)\)表示\(u,v\)两点的距离）。每次询问求满足条件的点个数。

解题思路：

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人，人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

珂朵莉，最可爱了呢。

---

我们定义\(f[i][j]\)为从点\(i\)出发，最短路小于等于\(j\)的点的集合。这个可以用bitset压位存储。

计算\(f[i][j]\)，我们首先要知道任意两点对间最短路，然后计算出从每个点出发，最短路恰好为\(j\)的点的集合。然后前缀或一遍就是\(f[i][j]\)。

计算都可以在\(O(\dfrac{n^3}{\omega})\)的复杂度内完成。

而求任意点对间最短路，就从每个点开始BFS一遍即可。时间复杂度\(O(n(n+m))\)。

最后处理询问的时候，就把每个\((x,y)\)对应的\(f[x][y]\)都取并集，然后求其中1的个数即可。时间复杂度\(O(\dfrac{n\sum a}{\omega})\)。

总时间复杂度\(O(n(n+m)+\dfrac{n^3+n\sum a}{\omega})\)，空间复杂度\(O(\dfrac{n^3}{\omega})\)。

然后听说这道题卡前向星

似乎是由于访问连续内存会比较快的原因，用vector存边就跑的飞快，而前向星就T飞了。

C++ Code：

#include<bitset>

#include<cstdio>

#include<cctype>

#include<queue>

#include<vector>

#define N 1003

#ifdef ONLINE_JUDGE

struct istream{

	char buf[23333333],*s;

	inline istream(){

		buf[fread(s=buf,1,23333330,stdin)]='\n';

		fclose(stdin);

	}

	inline istream&operator>>(int&d){

		d=0;

		for(;!isdigit(*s);++s);

		while(isdigit(*s))

		d=(d<<3)+(d<<1)+(*s++^'0');

		return*this;

	}

}cin;

#else

#include<iostream>

using std::cin;

#endif

std::bitset<N>a[N][N];

int n,m,q,dis[N][N];

std::vector<int>G[N];

void bfs(int s,int*dis){

	for(int i=1;i<=n;++i)dis[i]=1002;

	static std::queue<int>q;

	dis[s]=0;

	for(q.push(s);!q.empty();){

		int u=q.front();q.pop();

		for(int i:G[u])

		if(dis[i]==1002){

			dis[i]=dis[u]+1;

			q.push(i);

		}

	}

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

	a[s][dis[i]].set(i);

	for(int i=1;i<=n;++i)a[s][i]|=a[s][i-1];

}

int main(){

	cin>>n>>m>>q;

	while(m--){

		int u,v;

		cin>>u>>v;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	for(int i=1;i<=n;++i)bfs(i,dis[i]);

	while(q--){

		std::bitset<N>ans;

		int x,u,v;

		cin>>x;

		while(x--){

			cin>>u>>v;

			if(v>n)v=n;

			ans|=a[u][v];

		}

		printf("%d\n",ans.count());

	}

	return 0;

}

巴特西

[Ynoi2015]我回来了

最新文章

热门文章