我是靠谱客的博主 怕黑墨镜,最近开发中收集的这篇文章主要介绍HDU 4827 Cycle Cocycle 01高斯消元 bitset加速 模板,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4827

题意

有一个n个点m条边的图,你要给每个点一个0或1的标号,使得每个点与偶数个相同标号的点之间有边。如果有多解输出任意一组。
题目保证一定有解。

思路

其实是sjt提醒我这题是高斯消元我才想到思路的,而且想了很久,自己觉得询问方案数,以及代数系统是模2的剩余系的题目,可能和高斯消元还是有一点关系把(比如比较经典的UVa 11542 HDU 5833)

如何建立方程是个难题,首先建立的方程组一定是 nn 的01方程组,但是这题一开始很难看出方程怎么和题目有联系了,先根据样例列一个方程看看:

?x1+1x2+1x3+1x4=?1x1+?x2+1x3+1x4=?1x1+1x2+?x3+0x4=?1x1+1x2+0x3+?x4=?

或者说是这样的增广矩阵
?1111?1111?0110?????

不妨考虑以下几个要素:
1. i行i列的取值是什么?也就是一个点建立出的方程要不要考虑它自己的取值?
2. 增广矩阵最后一列,也就是常数项的那一列取值应该是什么?

一个点列出的方程肯定和它周围节点相关的,枚举一个点在答案中的取值,于是可以列出下表:

答案中自身取值是否考虑自己的权值相邻点数常数项取值
0考虑偶数0
0考虑奇数1
0不考虑偶数0
0不考虑奇数1
1考虑偶数1
1考虑奇数1
1不考虑偶数0
1不考虑奇数0

接下来希望讲清楚自己的思路QAQ,根据上面列出的表格,可以发现:
- 当一个点周围有奇数个点的时候,把它的系数置为1,那它的常数项必为1
- 当一个点周围有偶数个点的时候,把它的系数置为0,那它的常数项必为0

所以就可以通过高斯消元求解了(雾

这里不用bitset优化就会TLE,所以自己参照大白和网上的一个题解写了一个模板

代码

此代码稍作修改后就可以用来求解HDU 5833

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
const int MAXN = 1e3 + 5;
int n, m;
bitset<MAXN> A[MAXN];
int x[MAXN];
// 建立线性方程组
// 建立出的方程组每行每列的第一个下标都是0
void setUpEquations(bitset<MAXN> A[MAXN]) {
// 清空原方程组
for (int i = 0; i < n; ++i) A[i].reset();
// 建立方程组, 具体问题具体分析
int u, v;
for (int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
--u; --v;
A[u].set(v); A[v].set(u);
}
for (int i = 0; i < n; ++i) if (A[i].count() & 1) {
A[i].set(i);
// 因为bitset的常数较小,为省方便
// 直接把增广矩阵的最后一列放在bitset的最后一列
A[i].set(MAXN - 1);
}
}
// 高斯-约当消元法
// m个方程, n个变量
void gauss(bitset<MAXN> A[MAXN], int *x, int m, int n) {
// 第一步,化为对角阵
int i = 0, j = 0, k, r, u;
while (i < m && j < n) {
r = i;
for (k = i; k < m; ++k) if (A[k][j]) {
r = k;
break;
}
if (A[r][j]) {
if (r != i) swap(A[r], A[i]);
for (u = i + 1; u < m; ++u) if (A[u][j]) A[u] ^= A[i];
++i;
}
++j;
}
int Rank = i;
// 矩阵已经化简为对角阵,如果只需要求出矩阵的秩
// (用于确定方程组有几组不同的解,如UVa 11542 HDU 5833)
// 直接 return Rank; 即可
// 第二步,回代变量,求解方程组
// 本题中默认自由变量值为0
for (i = 0; i < n; ++i) x[i] = 0;
for (i = Rank - 1; i >= 0; --i) {
if (A[i][MAXN - 1]) {
u = 0;
while (!A[i][u]) ++u;
x[u] = 1;
for (j = i - 1; j >= 0; --j) if (A[j][u]) {
A[j][u] = 0;
A[j].flip(MAXN - 1);
}
}
}
}
int main() {
//
freopen("in.txt", "r", stdin);
//
freopen("out.txt", "w", stdout);
int T, kase = 0;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
setUpEquations(A);
gauss(A, x, n, n);
printf("Case #%d:n", ++kase);
for (int i = 0; i < n; ++i) putchar('0' + x[i]);
putchar(10);
}
}

最后

以上就是怕黑墨镜为你收集整理的HDU 4827 Cycle Cocycle 01高斯消元 bitset加速 模板的全部内容,希望文章能够帮你解决HDU 4827 Cycle Cocycle 01高斯消元 bitset加速 模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(49)

评论列表共有 0 条评论

立即
投稿
返回
顶部