數學 --- 高斯消元 POJ 1830 -开发者知识库

數學 --- 高斯消元 POJ 1830 -开发者知识库,第1张

開關問題 

Problem's Link: http://poj.org/problem?id=1830


 

Mean: 


analyse:

增廣矩陣:con[i][j]:若操作j,i的狀態改變則con[i][j]=1,否則con[i][j]=0。

最后的增廣矩陣應該是N*(N 1),最后一列:對比開光的始末狀態,若相同則為0,若不同則為1;

 

最后的解共有三種:
1.無解,既出現了一行中前面N個數為0,第N 1的值非0;
2.沒有第1種情況出現,存在X行數值全為0,則解的個數為2^X;
3,沒有1,2 兩種情況出現,唯一解,輸出1。

Time complexity: O(n)

 

Source code: 

 

數學 --- 高斯消元 POJ 1830 -开发者知识库,第2张
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-06-17-22.36
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using namespace std;
const int p=30;
int con[p][p];
int N;
int beg[p],fin[p];
int function()
{
      int i,j,k,t,row,col,temp,count=0;
      for(row=col=1; row<=N&&col<=N; row  ,col  )
      {
            if(con[row][col]==0)
            {
                  for(i=row 1; i<=N; i  )
                  {
                        if(con[i][col]!=0)
                        {
                              for(j=1; j<=N 1; j  )
                              {
                                    swap(con[row][j],con[i][j]);
                              }
                              break;
                        }
                  }
            }
            if(con[row][col]==0)
            {
                  row--;
                  continue;
            }
            for(k=1; k<=N; k  ) 
            {
                  if(con[k][col]!=0&&k!=row)
                  {
                        temp=-(con[k][col]/con[row][col]);
                        for(t=col; t<=N 1; t  )
                        {
                              con[k][t]=(temp*con[row][t]) con[k][t];
                        }
                  }
            }
      }
      for(k=row; k<N 1; k  )
            if(con[k][N 1]!=0) { return 0; }
      if(row==N 1) { return 1; }
      else
      {
            return 1<<(N-row 1);
      }
}
int main()
{
      int T,i,j,x,y;
      scanf("%d",&T);
      while(T--)
      {
            scanf("%d",&N);
            for(i=1; i<=N; i  )
            {
                  scanf("%d",&beg[i]);
            }
            for(i=1; i<=N; i  )
            {
                  scanf("%d",&fin[i]);
            }
            scanf("%d%d",&x,&y);
            memset(con,0,sizeof(con));
            while(x!=0&&y!=0)
            {
                  con[y][x]=1;
                  scanf("%d%d",&x,&y);
            }
            for(i=1; i<=N; i  )
            {
                  con[i][i]=1;
            }
            for(i=1; i<=N; i  )
            {
                  if(beg[i]==fin[i])
                  {
                        con[i][N 1]=0;
                  }
                  else
                  {
                        con[i][N 1]=1;
                  }
            }
            int pp = function();
            if(pp)
            {
                  printf("%d\n",pp);
            }
            else
            {
                  printf("Oh,it's impossible~!!\n");
            }
      }
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复