三个题放在一起写了 主要是搞搞模板 在这里简述一下怎么写高斯消元
就和代数里学的加减消元学的一样 把矩阵化为上三角形形式 然后进行回代
同时枚举当前要消元的未知数和当前化简到哪一行了
然后从这一行往后 找这一列的一个不为0的系数
如果这一列以后的每一行都是0了 那么就说明当前这个未知数可以作为一个自由元 就是有无数解的意思
然后继续枚举下一个未知数
如果找到一个不为0的 和当前这一行的所有元素swap一下 然后除了这一行外 把其他所有行在这一列的系数消为0
最后答案存在每一行的第n + 1个位置
如果化简完了 如果存在后面的某一行 他的n + 1的值不等于0 那么就是无解
bzoj1013
#include <stdio.h> #include <algorithm> #include <cmath> #include <iostream> #include <string.h> using namespace std; double eps = 1e-9; int n; double a[15][15]; double zb[15][15]; void gauss() { int now = 1, to; for(int i = 1; i <= n; i++) { for(to = now; to <= n; to++) if(fabs(a[to][i]) > eps) break; if(to > n) continue; if(to != now) for(int j = 1; j <= n + 1; j++) swap(a[to][j], a[now][j]); double tmp = a[now][i]; for(int j = 1; j <= n + 1; j++) a[now][j] /= tmp; for(int j = 1; j <= n; j++) if(j != now) { tmp = a[j][i]; for(int k = 1; k <= n + 1; k++) a[j][k] -= tmp * a[now][k]; } now++; } } int main() { cin>>n; for(int i = 1; i <= n + 1; i++) { for(int j = 1; j <= n; j++) scanf("%lf", &zb[i][j]); if(i > 1) for(int j = 1; j <= n; j++) a[i - 1][j] = 2.0 * (zb[i][j] - zb[1][j]), a[i - 1][n + 1] += zb[i][j] * zb[i][j] - zb[1][j] * zb[1][j]; } gauss(); for(int i = 1; i <= n - 1; i++) printf("%.3lf ", a[i][n + 1]); printf("%.3lf ", a[n][n + 1]); return 0; }
bzoj1923 高斯消元的时间复杂度是n三方的 然后这个题数据是1000 10s居然水过去了 听说有用bitset优化的方法 (以后再学吧
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; int n, m, x, ans; int a[2005][1005]; void gauss1() { int now = 1, to; for(int i = 1; i <= n; i++) { for(to = now; to <= m; to++) if(a[to][i]) break; if(to > m) { ans = -1; return; } ans = max(ans, to); if(to != now) for(int j = 1; j <= n + 1; j++) swap(a[to][j], a[now][j]); for(int j = 1; j <= m; j++) if(j != now && a[j][i]) for(int k = 1; k <= n + 1; k++) a[j][k] ^= a[now][k]; now++; } } int main() { cin>>n>>m; for(int i = 1; i <= m; i++) { char s[1005]; scanf("%s %d", s, &x); int len = strlen(s); for(int j = 0; j < len; j++) a[i][j + 1] = s[j] - '0'; a[i][len + 1] = x; } gauss1(); if(ans == -1) puts("Cannot Determine"); else { printf("%d ", ans); for(int i = 1; i <= n; i++) { if(a[i][n + 1]) puts("?y7M#"); else puts("Earth"); } } return 0; }
POJ1830 入门题
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; int ans; int q[35]; int w[35]; int a[35][35]; void gauss(int n, int m) { ans = 0; int now = 1, to; for(int i = 1; i <= n; i++) { for(to = now; to <= m; to++) if(a[to][i]) break; if(to > m) { ans++; continue; } if(to != now) for(int j = 1; j <= n + 1; j++) swap(a[to][j], a[now][j]); for(int j = 1; j <= m; j++) if(j != now && a[j][i]) for(int k = 1; k <= n + 1; k++) a[j][k] ^= a[now][k]; now++; } for(int i = now; i <= m; i++) if(a[i][n + 1]) { ans = -1; return; } } int main() { int T; scanf("%d", &T); while(T--) { memset(a, 0, sizeof(a)); int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &q[i]); for(int i = 1; i <= n; i++) scanf("%d", &w[i]), w[i] ^= q[i], a[i][n + 1] = w[i]; for(int i = 1; i <= n; i++) a[i][i] = 1; int u, v; while(~scanf("%d%d", &u, &v) && u + v) a[v][u] = 1; gauss(n, n); if(ans == -1) puts("Oh,it's impossible~!!"); else printf("%d ", 1 << ans); } return 0; }