牛客挑战赛47 C.条件(bitset的简单应用)

传送门

一定存在的边放一起跑一边弗洛伊德

然后再加上可能存在的边跑弗洛伊德

这样是 O ( n 3 ) O(n^3) O(n3)

但是由于这里只需要判断是否连通,所以可以使用或运算、

也就是把每个点能到的点看成一个二进制数,这样可以使用 b i t s e t bitset bitset优化复杂度

#include bits/stdc++.h
using namespace std;
int n,m1,m2,q;
bitset1001bit1[1001],bit2[1001];
int main()
{
	cin  n  m1  m2   q;
	for(int i=1;i=n;i++) 
	for(int j=1;j=n;j++)
	{
		bit2[i][j]=1;
		if( i==j )	bit1[i][j] = 1;
	}
	for(int i=1;i=m1;i++)
	{
		int x,y; cin  x  y;
		bit1[x][y] = 1;	
	}
	for(int k=1;k=n;k++)
	for(int i=1;i=n;i++)
	{
		//正常来说枚举一个j,然后dis[i][j] |= dis[i][k]dis[k][j] 
		if( bit1[i][k]==0 )	continue;
		bit1[i] |= bit1[k];
	}
	for(int i=1;i=m2;i++)
	{
		int x,y; cin  x  y; bit2[x][y] = 0;
	}
	for(int k=1;k=n;k++)
	for(int i=1;i=n;i++)
	{
		//正常来说枚举一个j,然后dis[i][j] |= dis[i][k]dis[k][j] 
		if( bit2[i][k]==0 )	continue;
		bit2[i] |= bit2[k];
	}
	while( q-- )
	{
		int x,y; cin  x  y;
		if( bit1[x][y] )	cout  "Yes ";
		else	cout  "No ";
		if( bit2[x][y] )	cout  "Yes\n";
		else	cout  "No\n";
	}
}
最新回复(0)
/jishuwvP6OSeN66_2F74P8I8yOhlRLRUXeqnlVCqax2E02mSZ0_3D4834421
8 简首页