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

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

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

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

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
bitset<1510> m[1510];
```
```
 
```
```
int main(){
```
```
	int n,k; cin>>n>>k;
```
```
	for (int i=0;i<n;m[i].set(k),i++)
```
```
		for (int j=0;j<k;j++){
```
```
			int t; scanf("%d",&t);
```
```
			m[i][j]=t%2;
```
```
		}
```
```
	m[1500].set(k);
```
```
	int i=0;
```

	//for (int i=0;i<n;i++,cout<<'\n') for (int j=0;j<=k;j++) cout<<m[i][j]<<' ';

```
	for (int j=0;j<k;j++){
```
```
		for (int l=i;l<n;l++)
```
```
			if (m[l][j]){
```
```
				swap(m[l],m[i]);
```
```
				break;
```
```
			}
```
```
		if (m[i][j]==0) continue;
```
```
		for (int l=i+1;l<n;l++)
```
```
			if (m[l][j]==1) m[l]^=m[i];
```
```
		i++;
```
```
	}
```

	for (int i=0;i<n;i++) if (m[i]==m[1500]) return puts("No"),0;

```
	puts("Yes");
```
```
	return 0;
```
```
}
```

fffasttime

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

发表评论取消回复

发表评论 取消回复

发表评论取消回复