题目大意：给定一个n个点的有向图，求有多少点对(x,y),使x沿边可到达y
设f[i][j]为从i到j是否可达
首先强联通分量中的随意两个点均可达 于是我们利用Tarjan缩点
缩点之后是一个拓扑图。我们求出拓扑序，沿着拓扑序从后向前DP，状态转移方程为：
f[i][k]=or{ f[j][k] } (i有直连边到达j,1<=k<=n,n为强连通分量的个数)
鉴于每一个点的值仅仅会是1或者0。所以我们能够直接状压，或者干脆开bitset，总体取或就可以
时间复杂度O(mn/32)
今天各种手滑。。。
Tarjan不赋值dpt和low，拓扑序求出来不用。各种调用错数组。。。最终彻底脑残了好开心233 QAQ
#include#include #include #include #include #define M 2014using namespace std;int n,ans,map[M][M],topo_map[M][M];int dpt[M],low[M],v[M],cnt,belong[M],siz[M],_n,stack[M],top;int into[M],q[M],r,h;bitset f[M];void Tarjan(int x){ int y; dpt[x]=low[x]=++cnt; stack[++top]=x; for(y=1;y<=n;y++) if(map[x][y]) { if(v[y]) continue; if(dpt[y]) low[x]=min(low[x],dpt[y]); else Tarjan(y),low[x]=min(low[x],low[y]); } if(dpt[x]==low[x]) { int t; ++_n; do{ t=stack[top--]; belong[t]=_n; v[t]=1; ++siz[_n]; }while(t!=x); }}void Topology_Sort(){ int i,y; for(i=1;i<=_n;i++) if(!into[i]) q[++r]=i; while(r!=h) { int x=q[++h]; for(y=1;y<=_n;y++) if(topo_map[x][y]) { into[y]--; if(!into[y]) q[++r]=y; } }}int main(){ int i,j,x; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%1d",&map[i][j]); for(i=1;i<=n;i++) if(!v[i]) Tarjan(i); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j]&&belong[i]!=belong[j]) { if(!topo_map[belong[i]][belong[j]]) into[belong[j]]++; topo_map[belong[i]][belong[j]]=1; f[belong[i]][belong[j]]=1; } for(i=1;i<=_n;i++) f[i][i]=1; Topology_Sort(); for(i=_n;i;i--) { x=q[i]; for(j=1;j<=_n;j++) if(topo_map[x][j]) f[x]|=f[j]; } for(i=1;i<=_n;i++) for(j=1;j<=_n;j++) if(f[i][j]) ans+=siz[i]*siz[j]; cout< <