Gym101611 I 判断线性空间是否为二分图

题意:k维线性空间上,给定n个k维整数向量v1,v2,…,vn。以线性空间的任意元素a为图的定点,连接所有(a,a+vi)。保证最终图连通,判断是否为二分图。

1=<k<=n<=1500, 保证输入没有零向量。

把向量列成矩阵,并在最右侧增加一列1代表路径长度。对矩阵两行相加减等价于连接两条路径。存在奇环等价于变换出一个零向量的行,但最后一列为奇数。注意到可以仅保留上述矩阵的奇偶性而不影响判断(例如假设两行为不同偶数,可以把它消至0,但不会改变最后一列的奇偶性)。于是就是一个对01矩阵消元的操作,用bitset加速即可。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bitset<1510> m[1510];
  5.  
  6. int main(){
  7. 	int n,k; cin>>n>>k;
  8. 	for (int i=0;i<n;m[i].set(k),i++)
  9. 		for (int j=0;j<k;j++){
  10. 			int t; scanf("%d",&t);
  11. 			m[i][j]=t%2;
  12. 		}
  13. 	m[1500].set(k);
  14. 	int i=0;
  15. 	//for (int i=0;i<n;i++,cout<<'\n') for (int j=0;j<=k;j++) cout<<m[i][j]<<' ';
  16. 	for (int j=0;j<k;j++){
  17. 		for (int l=i;l<n;l++)
  18. 			if (m[l][j]){
  19. 				swap(m[l],m[i]);
  20. 				break;
  21. 			}
  22. 		if (m[i][j]==0) continue;
  23. 		for (int l=i+1;l<n;l++)
  24. 			if (m[l][j]==1) m[l]^=m[i];
  25. 		i++;
  26. 	}
  27. 	for (int i=0;i<n;i++) if (m[i]==m[1500]) return puts("No"),0;
  28. 	puts("Yes");
  29. 	return 0;
  30. }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注