BZOJ 2208: [JSOI2010]连通数 SCC Topsort bitset

title

BZOJ 2008

LUOGU 4306

简化题意：

analysis

这题暴力 \(floyed~O(n^3)\) 可过。

然后我想到了一个最显然的算法，每个点都遍历一遍，复杂度应该是 \(O(nm)\) ，差不多可过啊。

在将近刷了一版后，我突然想到 \(m=n^2\) ，靠，这还是 \(O(n^3)\) ，而且比 \(floyed\) 还要慢些的，不过卡到了 \(91pts\) 。

然后就去想正解了，其实也比较简单了。

有向图，联通，基本就指向 \(SCC\) 了，那就 \(O(n)\) 求个 \(SCC\) ，然后缩点建反图跑一遍 \(Topsort\) ， \(Topsort\) 的时候开一个 \(bitset\) 来更新每个连通块的连通性，最后 \(O(tot^2)\) 统计一下就好了（ \(tot\) 指连通块个数）。

统计也比较显然了，枚举连通块，如果两个连通块能够到达，那么答案就加上它们的大小的乘积，哦了，看 \(code\) 吧。

code

\(91pts\)

#pragma GCC optimize(3,"Ofast","inline")

#include<bits/stdc++.h>

#define file(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)

#define G ch=getchar()
#define DeBug(x) std::cout<<#x<<':'<<x<<std::endl

const int MaxN=2e3+5, MaxM=MaxN*MaxN;

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, G;
        while (!isdigit(ch) && ch^'-') G;
        if (ch=='-') f=-1, G;
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), G;
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

template<typename T>inline bool chkMin(T &a,const T &b) { return a>b ? (a=b, true) : false; }
template<typename T>inline bool chkMax(T &a,const T &b) { return a<b ? (a=b, true) : false; }
template<typename T>inline T min(T a,T b) { return a<b ? a : b; }
template<typename T>inline T max(T a,T b) { return a>b ? a : b; }

int ver[MaxM], Next[MaxM], head[MaxN], len=1;
inline void add(int x, int y)
{
    ver[++len]=y, Next[len]=head[x], head[x]=len;
}

int ans;
bool vis[MaxN];
inline void dfs(int x, int fa)
{
    ++ans;
    vis[x]=1;
    for (int i=head[x]; i; i=Next[i])
    {
        int y=ver[i];
        if (vis[y]) continue;
        dfs(y, x);
    }
}

char s[MaxN];
int main()
{
    int n; read(n);
    for (int i=1; i<=n; ++i)
    {
        scanf("%s", s+1);
        for (int j=1; j<=n; ++j)
            if (s[j]=='1') add(i, j);
    }

    for (int i=1; i<=n; ++i)
    {
        memset(vis, 0, sizeof(vis));
        dfs(i, 0);
    }
    write(ans, '\n');
    IO::flush();
    return 0;
}

\(100pts\)

#include<bits/stdc++.h>

#define file(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)

#define Grt ch=getchar()
#define DeBug(x) std::cout<<#x<<':'<<x<<std::endl

const int MaxN=2e3+5, MaxM=MaxN*MaxN;
typedef int iarr[MaxN];

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, Grt;
        while (!isdigit(ch) && ch^'-') Grt;
        if (ch=='-') f=-1, Grt;
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), Grt;
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

template<typename T>inline bool chkMin(T &a,const T &b) { return a>b ? (a=b, true) : false; }
template<typename T>inline bool chkMax(T &a,const T &b) { return a<b ? (a=b, true) : false; }
template<typename T>inline T min(T a,T b) { return a<b ? a : b; }
template<typename T>inline T max(T a,T b) { return a>b ? a : b; }

struct Graph
{
    int ver[MaxM], Next[MaxM], head[MaxN], len;
    inline void add(int x, int y)
    {
        ver[++len]=y, Next[len]=head[x], head[x]=len;
    }
} G, A;

namespace SCC
{
    iarr dfn, low, Stack, belong, siz;
    bool instack[MaxN];
    int id, top, tot;
    inline void tarjan(int x)
    {
        dfn[x]=low[x]=++id;
        Stack[++top]=x;
        instack[x]=1;
        for (int i=G.head[x]; i; i=G.Next[i])
        {
            int y=G.ver[i];
            if (!dfn[y])
            {
                tarjan(y);
                chkMin(low[x], low[y]);
            }
            else if (instack[x]) chkMin(low[x], dfn[y]);
        }
        if (low[x]==dfn[x])
        {
            int k;
            ++tot;
            do
            {
                k=Stack[top--];
                ++siz[tot];
                belong[k]=tot;
                instack[x]=0;
            } while (k!=x);
        }
    }
}

using SCC::tarjan;
using SCC::dfn;
using SCC::siz;
using SCC::belong;
using SCC::tot;

char s[MaxN];
int deg[MaxN];
int main()
{
    int n; read(n);
    for (int i=1; i<=n; ++i)//建出原图
    {
        scanf("%s", s+1);
        for (int j=1; j<=n; ++j)
            if (s[j]=='1') G.add(i, j);
    }

    for (int i=1; i<=n; ++i)//求出scc
        if (!dfn[i]) tarjan(i);

    for (int x=1; x<=n; ++x)//建出缩点后的图
        for (int i=G.head[x]; i; i=G.Next[i])
        {
            int y=G.ver[i];
            if (belong[x]^belong[y]) A.add(belong[y], belong[x]), ++deg[belong[x]];
        }

    std::bitset<MaxN> f[MaxN];
    for (int i=1; i<=tot; ++i) f[i][i]=1;//bitset赋初值

    std::queue<int> q;
    for (int i=1; i<=tot; ++i)//topsort
        if (!deg[i]) q.push(i);
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        for (int i=A.head[x]; i; i=A.Next[i])
        {
            int y=A.ver[i];
            f[y]|=f[x];
            if (!--deg[y]) q.push(y);
        }
    }
    int ans=0;
    for (int i=1; i<=tot; ++i)
        for (int j=1; j<=tot; ++j)
            if (f[i][j]) ans+=siz[i]*siz[j];//统计answer
    write(ans, '\n');
    IO::flush();
    return 0;
}