题意:
给一个有向连通图,问连通的点对数。
题解:
裸的传递闭包,但是因为数据较大,n^3会T,所以需要加bitset优化。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int n;
char s[2009];
bitset<2009> a[2009];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%s",s+1);
for (int j = 1; j <= n; j++)
a[i][j]=s[j]-'0';
a[i][i] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
if (a[i][k])
a[i] |= a[k];
int ans = 0;
for (int i = 1; i <= n; i++)
ans += a[i].count();
printf("%d\n", ans);
return 0;
}