【算法笔记】bitset优化传递闭包

前言

打了一场模拟赛，T2大意是求不同的起点终点选择方案数，想到了floyd传递闭包在矩阵中求和，加上特殊性质得了55，后来听说用bitset优化可以过，震撼

bitset

一个stl容器，用了状态压缩的思想，空间和时间都有优化，具体上大概优化了$\frac{1}{w}$的常数（其中$w$取决于系统，一般是64）

用法这里就不讲了，具体上网搜（其实直接当二维bool数组用就行）

例题

B3611【模板】传递闭包

最基础的，传递闭包的板子题。

未用bitset优化的传递闭包

复杂度$O(n^3)$，大概能过200的数据

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) cin>>a[i][j];
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) a[i][j]|=a[i][k]&&a[k][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cout<<a[i][j]<<" ";
		cout<<endl;	
	}
}

用bitset优化的传递闭包

复杂度$O(\frac{1}{w}n^3)$，亲测过了2000的数据

#include<bits/stdc++.h>
using namespace std;
const int N=110;
bitset<N>a[N];
int n,d;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) scanf("%d",&d),a[i][j]=d;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++) if(a[i][k]) a[i]|=a[k];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) d=a[i][j],printf("%d ",d);
		putchar('\n');
	}
}