首页 > 代码库 > Poj1830开关问题,高斯消元
Poj1830开关问题,高斯消元
高斯消元的入门题。
#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>using namespace std;int Map[100][100];int gauss(int equ, int var){ int k; int col; for (k = 0, col = 0; k < equ&&col < var; k++, col++){ int kk = k; for (int i = k + 1; i < equ; i++){ if (Map[i][col]>Map[kk][col])kk = i; } if (kk != k){ for (int j = k; j <= var; j++) swap(Map[k][j], Map[kk][j]); } if (Map[k][col] == 0){ k--; continue; } for (int i = k + 1; i < equ; i++){ if (Map[i][col]){ for (int j = col; j <= var; j++){ Map[i][j] ^= Map[k][j]; } } } } for (int i = k; i < equ; i++){ if (Map[i][col]) return -1; } return col - k;}int main(){ int k; int n; int a[100], b[100]; int c; int d; cin >> k; while (k--){ cin >> n; memset(Map, 0, sizeof(Map)); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) scanf("%d", &b[i]); for (int i = 0; i < n; i++) a[i] = (a[i] ^ b[i]); for (int i = 0; i < n; i++) Map[i][n] = a[i]; for(int i =0;i<n;i++) Map[i][i] = 1; while (cin >> c >> d, c || d){ c--;d--; Map[d][c] = 1; } int ans = 1; int t = gauss(n, n); if(t==-1){ cout<<"Oh,it‘s impossible~!!"<<endl; continue; } for (int i = 0; i < t; i++) ans *= 2; cout << ans << endl; } return 0;}
Poj1830开关问题,高斯消元
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。