傳送地址：https://www.luogu.com.cn/problem/P4306
題目描述
度量一個有向圖連通情況的一個指標是連通數，指圖中可達頂點對個的個數，
如圖
頂點 11 可達 1, 2, 3, 4, 51,2,3,4,5
頂點 22 可達 2, 3, 4, 52,3,4,5
頂點 33 可達 3, 4, 53,4,5
頂點 4, 54,5 都只能到達自身，
所以這張圖的連通數為 1414，
給定一張圖，請你求出它的連通數
題解
這題打了半天，發現用dfs或者bfs都是會TLE
于是就想采用另一種方法：bitset
這樣我們就可以用0代表不能到達，1代表可以到達
最后對對可以到的的進行求和即可
另外，關于bitset的使用以及函式呼叫，請參考：https://cplusplus.com/reference/bitset/bitset/?kw=bitset
其他就不多贅述了，
AC代碼：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=2e3+5; 4 bitset<N> B[N];//給每一個節點建立bitset 5 int main() 6 { 7 int n;cin>>n; 8 for(int i=1;i<=n;i++){ 9 string s;cin>>s; 10 for(int j=1;j<=n;j++){ 11 if(s[j-1]=='1'||i==j) B[i][j]=1; 12 //能到這個節點或者自己 13 } 14 } 15 for(int i=1;i<=n;i++){ 16 for(int j=1;j<=n;j++){ 17 if(B[j].test(i)) B[j]|=B[i]; 18 //如果j可以到達i，則i可以到達的所有節點j都能到達 19 //這里的“|”在此不在講述 20 } 21 } 22 int ans=0; 23 for(int i=1;i<=n;i++) ans+=B[i].count();//計算有多少個1 24 cout<<ans<<endl; 25 return 0; 26 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/521768.html
標籤：C++
上一篇：C++物件模型：g++實作（二）