首页 > 代码库 > 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开关问题,高斯消元