2208: [Jsoi2010]连通数

Time Limit: 20 Sec  

Memory Limit: 512 MB

Submit: 2383  

Solved: 1013

[ ][ ][ ]

Description

Input

输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。

Output

输出一行一个整数，表示该图的连通数。

Sample Input

3
010
001
100

Sample Output

9

HINT

 

对于100%的数据，N不超过2000。

 

Source

[ ][ ][ ]

【题解】【dfs||Tarjan算法+拓扑序+dp】

[way 1]【朴素dfs,直接暴力，只是，时间不大科学。我刚开始想像初始化树的方式来搞，但是由于有环，搞成了死循环】

[way 2]【一个比较科学的方法，先用Tarjan将环缩成一个点，然后，重新反向建图，按拓扑序处理，g[i][j]表示从i号点出发，状态为j的情况是否存在。用bitset处理】

dfs卡时A码：

 

#include
    
     #include
     
      #include
      
       using namespace std;int a[4000010],nxt[4000010],p[2010],tot;int n,dis[2010],ans;bool vis[2010];inline void add(int x,int y){	tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot;}void dfs(int x){	dis[x]=1; vis[x]=1;	for(int i=p[x];i!=-1;i=nxt[i])	 if(!vis[a[i]])	  {	  	dfs(a[i]);	  	dis[x]+=dis[a[i]];	  }}int main(){	int i,j;	memset(p,-1,sizeof(p));	memset(nxt,-1,sizeof(nxt));	scanf("%d\n",&n);	for(i=1;i<=n;++i)	 {	 	char s[2010];	 	scanf("%s",s+1);	 	for(j=1;j<=n;++j) 	 	 if(s[j]=='1') add(i,j);	 }	for(i=1;i<=n;++i)	 {	 	memset(vis,0,sizeof(vis));	 	memset(dis,0,sizeof(dis));	 	dfs(i); ans+=dis[i];	 }	printf("%d\n",ans);	return 0;}
      
     
    

Tarjan算法+拓扑序+dp：

 

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;bitset<2010>g[2010];queue
         
          que;int a[4000010],nxt[4000010],p[2010],tot;int a1[4000010],Nxt[4000010],point[2010],tt;int dft[2010],dis[2010],size[2010],root,cnt;int d[50010],top,f[2010],in[2010];int n,ans;bool vis[2010],ch[2010][2010];inline void add(int x,int y){ tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot;}inline void Add(int x,int y){ tt++; a1[tt]=y; Nxt[tt]=point[x]; point[x]=tt;}void tarjan(int x){ dis[x]=dft[x]=++cnt; d[++top]=x; vis[x]=1; for(int i=p[x];i!=-1;i=nxt[i]) if(!dft[a[i]]) { tarjan(a[i]); dis[x]=min(dis[x],dis[a[i]]); } else if(vis[a[i]]&&dis[x]>dft[a[i]]) dis[x]=dft[a[i]]; if(dis[x]==dft[x]) { ++root; int b; do{ b=d[top--]; size[root]++; f[b]=root; vis[b]=0; }while(x!=b); } return;}inline void solve(){ for(int i=1;i<=root;++i) g[i][i]=1; for(int i=1;i<=root;++i) if(!in[i]) que.push(i); while(!que.empty()) { int u=que.front(); que.pop(); for(int i=point[u];i!=-1;i=Nxt[i]) { g[a1[i]]|=g[u]; in[a1[i]]--; if(!in[a1[i]]) que.push(a1[i]); } } for(int i=1;i<=root;++i) for(int j=1;j<=root;++j) if(g[i][j]) ans+=size[i]*size[j]; return;}int main(){ int i,j; memset(p,-1,sizeof(p)); memset(nxt,-1,sizeof(nxt)); scanf("%d\n",&n); for(i=1;i<=n;++i) { char s[2010]; scanf("%s",s+1); for(j=1;j<=n;++j) if(s[j]=='1') add(i,j); } for(i=1;i<=n;++i) if(!dft[i]) tarjan(i); memset(Nxt,-1,sizeof(Nxt)); memset(point,-1,sizeof(point)); for(i=1;i<=n;++i) for(j=p[i];j!=-1;j=nxt[j]) if(f[i]!=f[a[j]]&&!ch[f[a[j]]][f[i]]) Add(f[a[j]],f[i]),ch[f[a[j]]][f[i]]=1,in[f[i]]++; solve(); printf("%d\n",ans); return 0;}