[at] abc 258G - Triangle 三元組可達-暴力

前言

$tag:$bitset01圖
傳送門:

題意 :
給定一個$01$完全圖,$1$錶示這兩個點有邊相連,$0$錶示這兩個點沒有邊相連

詢問有多少組三元組$(i,j,k)$,滿足兩兩之間有邊相連

思路 :

暴力的做法$n^3$,因為圖只存在$01$,我們考慮使用比特運算减去一層的枚舉

即bitset , 我們將狀態存入biset中,然後枚舉兩行之間的狀態,進行$\&$運算

顯然的如果$\&=1$那麼,存在三個點是可達的,時間複雜度$n^{2}logn$

code :

void solve(){
    
	int n;cin>>n;
	vector<bitset<N>> v(n);
	vector<string> s(n);
	
	for(int i = 0; i < n; i ++ ){
    
		cin>>s[i];
		
		for(int j = 0 ; j < n ; j ++ ){
    
			if(s[i][j] == '1') v[i][j] = 1;
		}
	}
	
	ll ans = 0 ;
	for(int i = 0 ; i< n ; i ++ ){
    
		for(int j = 0 ; j< i ; j ++ ){
    
			if(s[i][j] == '1') ans += (v[i]&v[j]).count();
		}
	}
	
	cout<<ans/3<<endl;
	
}

int main(){
    
	//int t;cin>>t;while(t--)
    solve();
    return 0 ;
}