luogu P4306 [JSOI2010]连通数

传送门

还是比较难的

首先题意就容易看错

要求的是有向图单向可达点对数目

考虑环中一定是互相可达的

所以先缩点然后统计好内部的贡献是sze[col]的平方

再dp一下就行

话说输出N^2有90 

另:有一个非标准做法就是O(N^3)搞一个传递闭包

然后用bitset卡常1/32

坑点就是(i->i)是要算到答案里的......

Time cost:55min

Code:

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
#define rep(i,a,n) for(int i = a;i <= n;i++)
const int N = 2005;
//head
int n,ans;
char s[N];
bitset<N> dp[N];
int main() {
    scanf("%d",&n);
    rep(i,1,n) {
    scanf("%s",s+1);
    rep(j,1,n) dp[i][j] = (s[j] == '1' || j == i);
    }
    rep(i,1,n) rep(j,1,n) {
    if(dp[j][i]) dp[j] |= dp[i];
    //bitset you_hua O(n^3/32)
    }
    rep(i,1,n) ans += dp[i].count();
    printf("%d
",ans);
    return 0;
}