[刷题笔记] P2881

SXqwq's Library / 2024-02-20 / 原文

例题：P2881

注意到 $n \le 1000$。数据较小。且有传递性，即如果 $x,y$ 关系确定，$y,z$ 关系确定，那么 $x,z$ 关系确定。考虑传递闭包。

传递闭包从关系图的角度来说，如果原图上存在一条 $u,v$ 路径，那么传递闭包就将 $u,v$ 连边。

传递闭包可以使用 Floyd 算法解决。枚举中间点 $k$，如果 $\{i,k\}\{k,j\}$ 关系确定，那么 $\{i,j\}$ 关系确定。

传递闭包 Floyd 算法如下：

void Floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++) f[i][j] |= (f[i][k] && f[k][j]);
		}
	}
}

但此时的时间复杂度是 $O(n^3)$ 级别。无法接受。

我们只需要枚举每条边即可。对于边 $i,j$ ，如果 $i,j$ 有边，则能走到 $i$ 的一定能走到 $j$。转移即可。这里可以使用 bitset 优化。

对于本题，我们已知一些关系，基于这些关系跑传递闭包即可。

参考代码如下

#include <bits/stdc++.h>
using namespace std;
const int N = 10010; 
bitset <N> b[N];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		b[x][y] = 1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if( b[j][i])
			{
				b[j] |= b[i];
			}
		}
	}
	int ans = n*(n-1)/2;
	for(int i=1;i<=n;i++) ans -= b[i].count();
	cout<<ans<<endl;
	return 0;
}