欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ2208:连通数(强连通 & bitset)

程序员文章站 2024-03-19 12:56:28
...

2208: [Jsoi2010]连通数

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 3376  Solved: 1476
[Submit][Status][Discuss]

Description

BZOJ2208:连通数(强连通 & bitset)

Input

输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。

Output

输出一行一个整数,表示该图的连通数。

Sample Input

3
010
001
100

Sample Output

9

HINT

对于100%的数据,N不超过2000。

Source

思路:显然强连通分量里的点可以互达,所以先缩点重建DAG,然后计算DAG里面每个点可以达到的哪些点即可,开始没想到用bitset,因为之前被bitset的效率坑过几次,这里数据量不多就可以用一下。

# include <iostream>
# include <cstdio>
# include <vector>
# include <bitset>
using namespace std;
const int maxn = 2e3+30;
vector<int>G[maxn],g[maxn];
bitset<maxn>b[maxn];
char s[maxn][maxn];
int dep[maxn], low[maxn], in[maxn], stk, cnt, tot, ans;
int belong[maxn], num[maxn], st[maxn*2], in_st[maxn], vis[maxn];
void dfs(int u)
{
    dep[u] = low[u] = ++cnt;
    st[++stk] = u;
    in_st[u] = 1;
    for(int j=0; j<G[u].size(); ++j)
    {
        int v = G[u][j];
        if(!dep[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if(in_st[v] && dep[v] < low[u])
            low[u] = dep[v];
    }
    if(low[u] == dep[u])
    {
        ++tot;
        int j;
        do
        {
            j = st[stk--];
            belong[j] = tot;
            in_st[j] = 0;
            ++num[tot];
        }while(j != u);
    }
}
void dfs2(int u)
{
    if(vis[u]) return;
    vis[u] = 1;
    for(int j=0; j<g[u].size(); ++j)
    {
        int v = g[u][j];
        dfs2(v);
        b[u] |= b[v];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%s",s[i]);
        for(int j=0; s[i][j]; ++j)
            if(s[i][j]-'0')
                G[i].push_back(j+1);
    }
    for(int i=1; i<=n; ++i)
        if(!dep[i])
            dfs(i);
    for(int i=1; i<=n; ++i)
    {
        for(int k=0; k<G[i].size(); ++k)
        {
            int j=G[i][k];
            if(belong[i] != belong[j])
            {
                g[belong[i]].push_back(belong[j]);
                ++in[belong[j]];
            }
        }
    }
    for(int i=1; i<=tot; ++i)
        b[i][i] = 1;
    for(int i=1; i<=tot; ++i)
        if(in[i] == 0) dfs2(i);
    for(int i=1; i<=tot; ++i)
        for(int j=1; j<=tot; ++j)
        if(b[i][j]) ans += num[i]*num[j];
    printf("%d\n",ans);
    return 0;
}