Description
由于题目太短我直接上图罢
Analysis
题目描述非常简单，但是直接爆搜肯定会TLE，毕竟 \(n\leq 2000\)并且time limit=300ms。
我们发现如果题目保证无环直接topsort即可，问题就在环上，如何处理环呢？
我们可以缩点，缩点笔记，显然我们只需要统计答案数，缩完点后就变成了一个DAG，在DAG上跑topsort，统计答案统计上两个强连通分量祖先的儿子数乘积即可，显然若一个强连通分量祖先可以到达另一个强连通分量祖先，那么它们的儿子一定互相可达。
至于如何判断一个强连通分量可以到达另一个强连通分量呢？上文提到显然可以topsort，在topsort的时候可以开一个bitset优化一下，显然两个强连通分量祖先之间的关系要么为0要么为1（可达or不可达），直接bitset做运算继承关系即可。如果看起来很抽象见代码。
本题思路就这么简单，实现的时候需要注意很多细节。A了这道题，我对缩点有了更深刻的认识呢qwq
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
#include <stack>
using namespace std;
const int N=20500,M=4000500;
int n;
vector <int> Edge[N];
int dfn[N],low[N];
int cnt = 0;
int in_stack[N];
stack <int> s;
int vis[N];
int fa[N];
int fa_cnt = 0;
int fa_num[N];
bitset <N> new_map[N]; //bitset继承两个强连通分量祖先的关系
vector <int> new_Edge[N];
int ans = 0;
int in[N];
int v[N];
inline int read(){
register int x = 0, t = 1;
register char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
t=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*t;
}
inline void write(int x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int gc(){
int x=getchar();
if(x!='0'&&x!='1'){
return gc();
}
else{
return x;
}
}
void Tarjan(int pos)
{
dfn[pos] = low[pos] = ++cnt;
v[pos] = 1;
in_stack[pos] = 1;
s.push(pos);
for(int i=0;i<Edge[pos].size();i++)
{
if(!dfn[Edge[pos][i]])
{
Tarjan(Edge[pos][i]);
low[pos] = min(low[pos],low[Edge[pos][i]]);
}
else if(in_stack[Edge[pos][i]])
{
low[pos] = min(low[pos],dfn[Edge[pos][i]]);
}
}
if(dfn[pos] == low[pos])
{
fa_cnt ++;
while(s.top() != pos)
{
fa_num[fa_cnt] ++;
v[s.top()] = 0;
fa[s.top()] = fa_cnt;
in_stack[s.top()] = 0;
s.pop();
}
s.pop();
fa_num[fa_cnt] ++;
fa[pos] = fa_cnt;
in_stack[pos] = 0;
new_map[fa_cnt][fa_cnt] = 1; //显然每个祖先自己一定可以到达自己
}
}
void topsort()
{
queue <int> q; //使用队列进行topsort
for(int i=1;i<=fa_cnt;i++)
{
if(!in[i]) q.push(i);
}
while(!q.empty())
{
int noww = q.front();
q.pop();
for(int i=0;i<new_Edge[noww].size();i++)
{
new_map[new_Edge[noww][i]] |= new_map[noww]; //继承关系，显然只要有一个点可以到达另一个点则它们都可以到达那个点
in[new_Edge[noww][i]] --; //每个节点的入度
if(!in[new_Edge[noww][i]]) q.push(new_Edge[noww][i]);
}
}
}
int main()
{
n = read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
char flg=gc(); //奇怪的输入被卡了....
if(flg=='1') Edge[i].push_back(j);
}
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) Tarjan(i); //我们不保证原图一定联通，需要以每个点为root进行Tarjan，这个前提显然是该节点没有被访问，因为如果被访问过则已经操作了
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<Edge[i].size();j++)
{
if(fa[i] != fa[Edge[i][j]]) //建反图
{
bool can_push = true;
for(int k=0;k<new_Edge[fa[Edge[i][j]]].size();k++)
{
if(new_Edge[fa[Edge[i][j]]][k] == fa[i])
{
can_push = false;
break;
}
}
if(can_push)
{
new_Edge[fa[Edge[i][j]]].push_back(fa[i]);
in[fa[i]] ++;
}
}
}
}
topsort();
for(int i=1;i<=fa_cnt;i++)
{
for(int j=1;j<=fa_cnt;j++)
{
if(new_map[i][j]) ans += fa_num[i]*fa_num[j];//统计答案
}
}
write(ans);
return 0;
}