传送门

这道题的题目描述看起来很奇怪。实际上的意思是要求在这个有向图之内能到达的点对有多少，解释一下题里的图片就是(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(5,5)一共14个。

先小声说一下这题固输n^2可以得到90pts……

然后我们首先考虑非常暴力的做法，就是先手tarjan缩点，存每个联通块里面的节点个数，在新图上直接进行dfs，把每个点所能到达的点搜出来就行。

我也不知道能跑多快……但是如上文所述你固输都有90所以数据比较水，我一共跑了50ms就过了。

#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')

using namespace std;
typedef long long ll;
const int M = ;
const int N = ;
const double eps = 1e-;
const double fi = 0.61803399;
const double fim = 0.38196601;

int read()
{
int ans = ,op = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-') op = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
ans *= ;
ans += ch - '';
ch = getchar();
}
return ans * op;
}

struct edge
{
int next,to,from;
}e[N<<],e1[N<<];
int n,g[M][M],dfn[M],low[M],stack[M],top,idx,cur,ecnt,head[M],sd[M],h[M],sz[M],ecnt1,q[M],curr,tot;
char s[M];
ll ans;
bool vis[M],pd[M];

void add(int x,int y)
{
e[++ecnt].to = y;
e[ecnt].from = x;
e[ecnt].next = head[x];
head[x] = ecnt;
}

void tarjan(int x)
{
low[x] = dfn[x] = ++idx;
vis[x] = ,stack[++top] = x;
for(int i = head[x];i;i = e[i].next)
{
if(!dfn[e[i].to]) tarjan(e[i].to),low[x] = min(low[x],low[e[i].to]);
else if(vis[e[i].to]) low[x] = min(low[x],low[e[i].to]);
}
if(low[x] == dfn[x])
{
int p;
cur++;
while(p = stack[top--])
{
sd[p] = cur,vis[x] = ,sz[cur]++;
if(x == p) break;
}
}
}

void dfs(int x)
{

tot += sz\[x\],pd\[x\] = ,q\[++curr\] = x;  
for(int i = h\[x\];i;i = e1\[i\].next)  
{  
if(pd\[e1\[i\].to\]) continue;  
dfs(e1\[i\].to);  
}  

}

int main()
{
n = read();
rep(i,,n)
{
scanf("%s",s);
rep(j,,n-) if(s[j] == '') add(i,j+);
}
rep(i,,n) if(!dfn[i]) tarjan(i);
rep(i,,ecnt)
{
int r1 = sd[e[i].from],r2 = sd[e[i].to];
if(r1 != r2)
{
e1[++ecnt1].to = r2;
e1[ecnt1].next = h[r1];
e1[ecnt1].from = r1;
h[r1] = ecnt1;
}
}
rep(i,,cur)
{
rep(i,,curr) q[i] = ;tot = ;
dfs(i);
rep(i,,curr) pd[q[i]] = ;
ans += tot * sz[i];
}
printf("%lld\n",ans);
return ;
}

这样很神奇你的搜索就过了……

之后我们再说一种别的做法，他有一个高大上的名字，叫Floyd传递闭包！

这个东西可以判断有向图两点之间是否连通，一开始它的形状和初始给定的邻接矩阵是一样的，不过大对角线上的点都变成了1.

正常的dp是三重循环枚举，dp[i][j] = dp[i][k] & dp[k][j]。不过这样枚举O（n^3）会T，然后我们发现只有能和不能到两种状态，所以我们引入一种强大的东西——bitset来帮我们优化。

使用bitset压缩一行的状态，这样的话转移方程就变成了dp[i] |= dp[j].这样我们只需要O（n^3/32）的复杂度，就可以过了。

看一下代码（炒鸡短）

#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')

using namespace std;
typedef long long ll;
const int M = ;
const double eps = 1e-;
const double fi = 0.61803399;
const double fim = 0.38196601;

int read()
{
int ans = ,op = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-') op = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
ans *= ;
ans += ch - '';
ch = getchar();
}
return ans * op;
}

bitset <> f[M];
int n;
char s[M];
ll ans;

int main()
{
n = read();
rep(i,,n)
{
scanf("%s",s);
rep(j,,n-) if(s[j] == '') f[i][j+] = ;
f[i][i] = ;
}
rep(i,,n)
rep(j,,n) if(f[j][i]) f[j] |= f[i];
rep(i,,n) ans += f[i].count();
printf("%lld\n",ans);
return ;
}