题意: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;
}