[刷题笔记] P2881

例题：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;
}