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
更多推荐
Luogu P4304
发布评论