icontofig | 发布于 2020-04-16 21:31:39 | 阅读量 550 | 高斯消元 bitset
发布于 2020-04-16 21:31:39 | 高斯消元 bitset

题目大意

给出n个k维向量vi,对于k维空间中所有点a,将点a与点a+vi连边,求问全部连接完的图能否完成黑白染色。

题解

黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。

考虑二分图形成的条件:不能出现奇环。

于是问题就转变成了如何判断图中是否会存在奇环。

但是这个题目明显不能用通常的搜索判环解决。

考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。

假设n个未知数xi,假设一个点想要回到自身,需要使用第i个向量xi次。

于是要形成环即向量方程:

x1v1 + x2v2 + ... + xnvn = 0有解。

所以如果要保证形成奇数环的话,就是加入以下一个方程

xxor x2 xor ... xor xn = 1

联立来解一个n元k+1维方程组。

将上面的向量方程拆分到k维k个方程,并将所有运算全都mod 2处理,即可让整个方程组变成一个异或方程组。

能形成二分图的条件就是方程组不存在解,否则就说明构成的图不是二分图。

使用高斯消元解决方程组判断解的问题。

但是高斯消元有一个问题,就是复杂度不对,为O(nk2)

不过由于这道题的方程组的运算只与二进制异或有关,所以可以把方程的参数放入bitset加速,最终复杂度为O(nk2/64)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
bitset<maxn>g[maxn];
int n,k,now,x;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= k;++j){
            cin >> x;
            g[j][i] = abs(x) % 2;
        }
    }
    for(int i = 1;i <= n+1;++i){
        g[k+1][i] = 1;
    }
    now = 0;
    for(int i = 1;i <= n;++i){
        int j = now + 1;
        while(j <= k+1 && g[j][i] == 0)j++;
        if(j > k+1)continue;
        else{
            now++;
            swap(g[now],g[j]);
        }
        for(j = now + 1;j <= k+1;++j)
            if(g[j][i])
                g[j] ^= g[now];
    }
    for(int i = now+1;i <= k+1;++i){
        if(g[i][n+1]){
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}


内容更新于: 2020-04-16 21:31:53
链接地址: http://blog.leanote.com/post/icontofig/b910da0a2925

上一篇: 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet

下一篇: CodeForces 600E.Lomsat gelral dsu on tree 树上启发式合并

550 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航