bitset优化传递闭包
时间复杂度 \(O(\frac{n^3}{w})\)
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define ll long long
using namespace std;
const int N=1005;
bitset<N> f[N];
int n;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n; int x;
F(i,1,n) F(j,1,n) cin>>x,f[i][j]=x;
F(j,1,n) F(i,1,n) if(f[i][j]) f[i]|=f[j];
//j放外层,即以j为中转点更新所有点的f
F(i,1,n){
F(j,1,n) cout<<f[i][j]<<' ';
cout<<'\n';
}
return 0;
}
标签:闭包,cout,int,cin,long,传递,bitset
From: https://www.cnblogs.com/superl61/p/17935600.html