「JSOI 2010」连通数

发表于 | | 阅读次数:
字数统计: 257 字

Description

题目链接：BZOJ 2208

在一个有向图中，如果点 $u$ 可以直接或间接到达点 $v$，那么称 $(u,v)$ 是可达顶点对。现在给出一个有向图，求出其中可达顶点对的对数。

数据范围：$n\le 2000$

Solution

我们很容易得到一个 $O(n^3)$ 的朴素算法：直接传递闭包！

这个过程是可以通过 $\text{bitset}$ 优化的，因此我们可以将常数减小通过本题（貌似这道题可以直接用 $O(nm)$ 的暴力水过）。

时间复杂度：$O(n^3/32)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <cstdio>
#include <bitset>
const int N=2005;
int n;
char s[N];
std::bitset<N> f[N];

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%s",s+1);
        for(int j=1;j<=n;++j) f[i][j]=s[j]=='1';
        f[i][i]=1;
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(f[j][i]) f[j]|=f[i];
    int ans=0;
    for(int i=1;i<=n;++i) ans+=f[i].count();
    printf("%d\n",ans);
    return 0;
}
0%