题干：

题解：

　　本题也就是 一个有向图，题干中也没有说是否有环，我们就需要tarjan缩一下点（有向图缩点需要判断是否在队中），再进行操作。                                                                     
100% 7000ms

　　dfs暴搜。枚举1～n 不断 dfs 求子树大小，统计答案。

Code：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define $ 2444
 4 using namespace std;
 5 int n,first[$],tot1,dfn[$],low[$],tar,sta[$],up,cir[$],len[$],ans[$];
 6 int second[$],tot2,circle,sum;
 7 bool judge[$];
 8 struct tree{    int to,next;    }a[$*$],b[$*$];
 9 inline int min(int x,int y){    return x<y?x:y;    }
10 inline void adda(int x,int y){
11     a[++tot1]=(tree){    y,first[x]    };
12     first[x]=tot1;
13 } 
14 inline void addb(int x,int y){
15     b[++tot2]=(tree){    y,second[x]    };
16     second[x]=tot2;
17 }
18 inline void tarjan(int x,int tmp=0){
19     dfn[x]=low[x]=++tar;
20     sta[++up]=x; judge[x]=1;
21     for(register int i=second[x];i;i=b[i].next){
22         int to=b[i].to;
23         if(!dfn[to]){
24             tarjan(to);
25             low[x]=min(low[x],low[to]);
26         }
27         else if(judge[to]) low[x]=min(low[x],dfn[to]);
28     }
29     if(dfn[x]==low[x]){
30         len[++circle]=0;
31         do{
32             tmp=sta[up--];
33             cir[tmp]=circle;
34             len[circle]++;
35             judge[tmp]=0;
36         }while(tmp!=x);
37     }
38 }
39 inline int dfs(int x,int ans=0){
40     judge[x]=1; ans=len[x];
41     for(register int i=first[x];i;i=a[i].next){
42         int to=a[i].to;
43         if(judge[to]) continue;
44         ans+=dfs(to);
45     }
46     return ans;
47 }
48 signed main(){
49     scanf("%d",&n);
50     for(register int i=1;i<=n;++i)
51         for(register int j=1;j<=n;++j){
52             char aa=getchar();
53             while(aa!='0'&&aa!='1') aa=getchar();
54             if(aa=='1') addb(i,j);
55         }
56     for(register int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
57     for(register int i=1;i<=n;++i)
58         for(register int j=second[i];j;j=b[j].next){
59             int to=b[j].to;
60             if(cir[i]!=cir[to]) adda(cir[i],cir[to]);
61         }
62     for(register int i=1,x;i<=n;++i){
63         x=cir[i];
64         if(ans[x]){    sum+=ans[x]; continue;    }
65         memset(judge,0,sizeof(judge));
66         ans[x]=dfs(x); sum+=ans[x];
67     }
68     printf("%d",sum);
69 }

View Code

 

100% 703ms

　　为什么时间复杂度会有这么大的差别呢？本体正解用到一个STL： bitset 。

　　回头看一下 7000ms 算法，我们之所以不断一遍一遍枚举，是因为当这张图存在割点或割边时，我们会将割点或割边上的点重复计算，最后也无法处理。而利用 bitset 就可以将 bitset 作为储存状态的一个工具，不断在 toposort 中用 “ | ” 操作更新答案并去重（在这里其实dfs 也可，之所以要用 toposort，是因为具有更出色的时间复杂度 O( 边数 ) ），最后统计一下各点 bitset 中含有 1 的个数即可。

Code：

 1 #include<cstdio>
 2 #include<queue>
 3 #include<bitset>
 4 #define $ 2444
 5 using namespace std;
 6 int n,first[$],tot1,dfn[$],low[$],tar,sta[$],up,cir[$],len[$],ans;
 7 int second[$],tot2,circle,out[$];
 8 bool judge[$];
 9 std::bitset<$> z[$];
10 struct tree{    int to,next;    }a[$*$],b[$*$];
11 inline int min(int x,int y){    return x<y?x:y;    }
12 inline void adda(int x,int y){
13     a[++tot1]=(tree){    y,first[x]    };
14     first[x]=tot1;
15 } 
16 inline void addb(int x,int y){
17     b[++tot2]=(tree){    y,second[x]    };
18     second[x]=tot2;
19 }
20 inline void toposort(){
21     queue<int> q;
22     for(register int i=1;i<=circle;++i) if(!out[i])  q.push(i);
23     while(q.size()){
24         int x=q.front(); q.pop();
25         for(register int i=first[x];i;i=a[i].next){
26             int to=a[i].to;
27             z[to]|=z[x];
28             out[to]--;
29             if(out[to]==0) q.push(to);
30         }
31     }
32 }
33 inline void tarjan(int x,int tmp=0){
34     dfn[x]=low[x]=++tar;
35     sta[++up]=x; judge[x]=1;
36     for(register int i=second[x];i;i=b[i].next){
37         int to=b[i].to;
38         if(!dfn[to]){
39             tarjan(to);
40             low[x]=min(low[x],low[to]);
41         }
42         else if(judge[to]) low[x]=min(low[x],dfn[to]);
43     }
44     if(dfn[x]==low[x]){
45         ++circle;
46         do{
47             tmp=sta[up--];
48             len[circle]++;
49             cir[tmp]=circle;
50             judge[tmp]=0;
51             z[circle][tmp]=1;
52         }while(tmp!=x);
53     }
54 }
55 signed main(){
56     scanf("%d",&n);
57     for(register int i=1;i<=n;++i)
58         for(register int j=1;j<=n;++j){
59             char ch=getchar();
60             while(ch!='1'&&ch!='0')  ch=getchar();
61             if(ch=='1')  addb(i,j);
62         }
63     for(register int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
64     for(register int i=1;i<=n;++i)
65         for(register int j=second[i];j;j=b[j].next){
66             int to=b[j].to;
67             if(cir[i]!=cir[to]) adda(cir[to],cir[i]),out[cir[i]]++;
68         }
69     toposort();
70     for(register int i=1;i<=circle;++i) 
71         ans+=z[i].count()*len[i];
72     printf("%d",ans);
73 }

View Code