icontofig | 发布于 2020-04-16 21:31:39 | 阅读量 550 | 高斯消元 bitset
发布于 2020-04-16 21:31:39 | 高斯消元 bitset
2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest I . Infinite Gift
题目大意给出n个k维向量vi,对于k维空间中所有点a,将点a与点a+vi连边,求问全部连接完的图能否完成黑白染色。 题解黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。 考虑二分图形成的条件:不能出现奇环。 于是问题就转变成了如何判断图中是否会存在奇环。 但是这个题目明显不能用通常的搜索判环解决。 考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。 假设n个未知数xi,假设一个点想要回到自身,需要使用第i个向量xi次。 于是要形成环即向量方程: x1v1 + x2v2 + ... + xnvn = 0有解。 所以如果要保证形
继续阅读