首页 > 代码库 > Graph Automata Player
Graph Automata Player
题目链接
- 题意:
给n个点的有向图,边以邻接矩阵形式给出,如果为1则有边,为0无边。然后给出0时刻每个点的一个值,为0或1,输入一个T,输出-T时刻每个点的值:确定的话就输出,不确定的话按照题目要求输出error信息
题目背景:t时刻,每个点有一个值,那么t+1时刻,如果一个点发出的边的终点值为一的个数为奇数个,那么t+1时刻这个点的值就是1;否则为0 - 分析:
奇数边为零,偶数边为一,异或就可以实现。假设t时刻每个点的值的向量为x,那么x乘以邻接矩阵(加法改成异或操作)得到的向量就是t+1时刻的每个点的值。那么,其实就是 邻接矩阵 * 邻接矩阵 * …… * 邻接矩阵 * goal = now(goal是要求的时间的值的列向量,now是当前的值的列向量)。快速幂解决邻接矩阵的T次幂,然后高斯消元即可。 - 思考:
其实高斯消元可以解决的问题,就是将矩阵求逆矩阵乘以等式右边,但是逆矩阵可能不存在。所以,可以用逆矩阵求解的都应该考虑到高斯消元,并且高斯消元还可以求逆矩阵不存在的情况(无解,多解)。
const int maxn = 310; struct Mat { int n, m; bool v[maxn][maxn]; Mat (int n = 0, int m = 0, int zero = 0) { this->n = n; this->m = m; if (zero) REP(i, n) REP(j, m) v[i][j] = false; } } ipt, now; Mat mul(Mat& a, Mat& b) { Mat ret(a.n, b.m, true); REP(i, a.n) REP(k, b.m) REP(j, a.m) { ret.v[i][k] ^= (a.v[i][j] & b.v[j][k]); } return ret; } Mat qpow(Mat& a, int b) { Mat ret(a.n, a.n); int cnt = 0; while (b) { if (b & 1) { if (cnt == 0) { cnt = 1; ret = a; } else ret = mul(ret, a); } b >>= 1; a = mul(a, a); } return ret; } bool a[maxn][maxn]; int gauss(int N, int M) { int r, c, pvt; bool flag; for (r = 0, c = 0; r < N && c < M; r++, c++) { flag = false; for (int i = r; i < N; i++) if (a[i][c]) { flag = a[pvt = i][c]; break; } if (!flag) { r--; continue; } if (pvt != r) for (int j = r; j <= M; j++) swap(a[r][j], a[pvt][j]); for (int i = r + 1; i < N; ++i) { if (a[i][c]) { a[i][c] = false; for (int j = c + 1; j <= M; ++j) if (a[r][j]) a[i][j] = !a[i][j]; } } } for (int i = r; i < N; i++) if (a[i][M]) return -1; if (r < M) return M - r; for (int i = M - 1; i >= 0; i--) { for (int j = i + 1; j < M; j++) if (a[i][j]) a[i][M] ^= a[j][M]; a[i][M] /= a[i][i]; } return 0; } int main() { int n, T; while (~RI(n)) { ipt.n = ipt.m = now.m = n; now.n = 1; REP(i, n) REP(j, n) RI(ipt.v[i][j]); REP(i, n) RI(a[i][n]); RI(T); ipt = qpow(ipt, T); REP(i, n) REP(j, n) a[i][j] = ipt.v[i][j]; int ret = gauss(n, n); if (ret == 0) REP(i, n) printf("%d%c", a[i][n], (i == n - 1 ? '\n' : ' ')); else if (ret > 0) puts("ambiguous"); else puts("none"); } return 0; }
Graph Automata Player
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。