洛谷4306 [JSOI2010]连通数

题意

定义图的连通数是每个点可以到达的点数之和，求一个有向图的联通数。

其中点数 $N\le 2000$ 。

题解

显然直接用 $\text{Floyd}$ 传递闭包是不现实的，于是我直接照题解用了bitset。

用 bitset $\text{s[i]}$ 表示 $i$ 与 $N$ 个点的连通情况。直接双重循环枚举用 | 合并起来即可。

需要注意自己和自己也要算，但给出的矩阵是不算的，所以需要写在后面。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

bitset <20005> s[20005];
ll n,dis[2005],ans;

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++)
    {
        char ch[2005]; scanf("%s",ch+1);
        for (ll j=1;j<=n;j++) s[i][j]=ch[j]-'0';
        s[i][i]=1; //写在后面防止被覆盖
    }
    for (ll j=1;j<=n;j++)
    {
        for (ll i=1;i<=n;i++)
        {
            if (!s[i][j]) continue;
            s[i]|=s[j];
        }
    }
    for (ll i=1;i<=n;i++) ans+=s[i].count();
    return !printf("%lld",ans);
}