题目链接

思路

floyd求一下传递闭包，然后统计每个点可以到达的点数。

会tle，用bitset优化一下。将floyd的最后一层枚举变成bitset。

代码

/*

* @Author: wxyww

* @Date:   2019-01-23 15:08:40

* @Last Modified time: 2019-01-23 15:22:52

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<bitset>

using namespace std;

typedef long long ll;

const int N = 2010;

bitset<N>f[N];

ll read() {

   ll x=0,f=1;char c=getchar();

   while(c<'0'||c>'9') {

      if(c=='-') f=-1;

      c=getchar();

   }

   while(c>='0'&&c<='9') {

      x=x*10+c-'0';

      c=getchar();

   }

   return x*f;

}

char s[N];

int main() {

   int n = read();

   for(int i = 1;i <= n;++i) {

      scanf("%s",s + 1);

      for(int j = 1;j <= n;++j)

         f[i][j] = s[j] - '0';

      f[i][i] = 1;

   }

   for(int k = 1;k <= n;++k)

      for(int i = 1;i <= n;++i)

         if(f[i][k]) f[i] |= f[k];

   ll ans = 0;

   for(int i = 1;i <= n;++i)

      ans += f[i].count();

   cout<<ans;

   return 0;

}