Luogu P4304

Luogu P4304"/>

Luogu P4304

写在前面

\(cb\)的\(AC\)史

Idea

• 先用\(dfs\)暴力
  • 对于每个点跑一遍\(dfs\),顺便记录一下\(Ans\)，
  • 但因为每次\(dfs\)是\(O(m)=O(n^2)\)的，所以总复杂度为\(O(n^3)\)
• 再用\(Floyd\)，不用说\(O(n^3)\)
  • 输入时因为\(a[i][i]=0\) ，但自己和自己是联通的，所以要改成1

• 最后用\(bfs+O_2\)，复杂度不用我说了吧 因为我不会

  • \(bfs\)，对每个点遍历其路径，然后\(+n\)(\(i\)和\(i\)肯定是联通的)

Code

Code1

//dfs
int n,ans;
char s[maxn][maxn];
bool vis[maxn];
inline void dfs(int x){ans++; vis[x]=true;for(int i=0;i<n;i++) if(s[x][i]=='1'&&!vis[i]) dfs(i);
}
signed main(){n=read();for(int i=0;i<n;i++) scanf("%s",s[i]);for(int i=0;i<n;i++){mem(vis,0);dfs(i);}printf("%d",ans);return 0;
}

Code2

//Floyd
int n,ans;
int b[maxn][maxn];
char a[maxn][maxn];
signed main(){n=read();for(int i=1;i<=n;i++){scanf("%s",a[i]+1);for(int j=1;j<=n;j++)if(a[i][j]=='1') b[i][j]=1;b[i][i]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(b[i][k]==1&&b[k][j]==1)b[i][j]=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(b[i][j]==1)ans++;printf("%d",ans);return 0;
}

Code3

//bfs
int vis[2001] ;
vector<int>e[2001];
ll ans=0;
int n ;
inline void bfs(int rt){queue<int> q;mem(vis,0);q.push(rt);vis[rt]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<e[x].size();i++)if(!vis[e[x][i]]){ans++;vis[e[x][i]]=1;q.push(e[x][i]);}}
}
string S ;
int main(){scanf("%d",&n) ;for(int i=1;i<=n;i++){cin>>S;for(int j=0;j<n;j++) if(S[j]=='1') e[i].push_back(j+1);}for(int i=1;i<=n;i++) bfs(i) ;printf("%d",ans+n);return 0;
}

\[ The \quad End \]

\[ \text{最渺小的我,有大大的梦.时间向前走一定只有路口没有尽头-《让我留在你身边》唐汉霄} \]

转载于:.html