当前位置:首页 > 资讯 > info5 > 正文

POJ 1830 开关问题 (高斯消元)

发表于: 2015-01-26   作者:u013013910   来源:转载   浏览:
摘要: 题目地址:POJ1830高斯消元第一发。一个地方逻辑判断出现了失误,调了一下午啊。。。通过高斯消元来找矩阵的秩,然后2^(自由元的数量)就是答案。因为对于每个自由元,都有0和1两种状态可选。代码如下:#include #include #include #include #include #include #include #include #include usingnamespacestd;

题目地址:POJ 1830

高斯消元第一发。一个地方逻辑判断出现了失误,调了一下午啊。。。

通过高斯消元来找矩阵的秩,然后2^(自由元的数量)就是答案。因为对于每个自由元,都有0和1两种状态可选。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
int a[35], b[35], d[35][35], n;
int gauss()
{
        int i, j, k, r, h;
        for(i=0,j=0; i<n&&j<n;i++,j++) {
                r=i;
                if(d[i][j]==0) {
                        for(k=i+1; k<n; k++) {
                                if(d[k][j]) {
                                        r=k;
                                        break;
                                }
                        }
                        if(k>=n){
                                i--;continue ;
                        }
                }
                if(r!=i) {
                        for(k=0; k<=n; k++) {
                                swap(d[i][k],d[r][k]);
                        }
                }
                for(k=i+1; k<n; k++) {
                        if(d[k][j]==0) continue ;
                        for(h=j; h<=n; h++) {
                                d[k][h]^=d[i][h];
                        }
                }
        }
        for(k=i; k<n; k++) {
                if(d[k][n]) return -1;
        }
        return 1<<n-i;
}
int main()
{
        int t, i, x, y, ans;
        scanf("%d",&t);
        while(t--) {
                scanf("%d",&n);
                memset(d,0,sizeof(d));
                for(i=0; i<n; i++) {
                        scanf("%d",&a[i]);
                }
                for(i=0; i<n; i++) {
                        scanf("%d",&b[i]);
                        if(a[i]!=b[i]) {
                                d[i][n]=1;
                        }
                        d[i][i]=1;
                }
                while(scanf("%d%d",&x,&y)!=EOF&&x+y) {
                        d[y-1][x-1]=1;
                }
                ans=gauss();
                if(ans<0) {
                        printf("Oh,it's impossible~!!\n");
                } else {
                        printf("%d\n",ans);
                }
        }
        return 0;
}


POJ 1830 开关问题 (高斯消元)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
EXTENDED LIGHTS OUT Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8353 Accepted:
Electric resistance Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Subm
EXTENDED LIGHTS OUT Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8390 Accepted:
高斯消元法(理论+习题) 高斯消元主要用来解多元一次线性方程组,主要用到的线性代数的知识详见矩
[转:http://www.cnblogs.com/pegasus/archive/2011/07/31/2123195.html] 高斯消元法(Gaussian eli
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 37055 Accepted: 16125 De
Painter's Problem Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5352 Accepted: 2
Language: Default EXTENDED LIGHTS OUT Time Limit: 1000MS Memory Limit: 10000K Total Submissio
EXTENDED LIGHTS OUT Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 6608 Accepted:
EXTENDED LIGHTS OUT Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 7817 Accepted:
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号