生活随笔
收集整理的這篇文章主要介紹了
poj 1830 开关问题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
高斯消元。
自由元個數res,最后答案因為每個變量有0,1 ? 狀態所以ans=1<<res;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-7;
int gauss(double a[][50],int n,int l[],double ans[]){int i,j,k;for(i=0;i<n;i++)l[i]=0;int r=0,res=0;for(i=0;i<n;i++){for(j=r;j<n;j++){if(fabs(a[j][i])>eps){for(k=i;k<=n;k++)swap(a[r][k],a[j][k]);break;}}if(fabs(a[r][i])<eps){res++;continue;}for(j=0;j<n;j++){if(j!=r&&fabs(a[j][i])>eps){double tmp=a[j][i]/a[r][i];for(k=i;k<=n;k++){a[j][k]-=tmp*a[r][k];}}}l[i]=1;r++;}for(i=0;i<n;i++)if(l[i])for(j=0;j<n;j++)if(fabs(a[j][i])>eps)ans[i]=a[j][n]/a[j][i];for(i=r;i<n;i++)if(fabs(a[i][n])>eps)return -1;return 1<<res;
}
int main()
{int t;scanf("%d",&t);while(t--){double dis[50][50];int l[50];double ans[50];int n,i;scanf("%d",&n);memset(ans,0,sizeof(ans));memset(dis,0,sizeof(dis));int a[50],b[50];for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++){scanf("%d",&b[i]);dis[i][n]=a[i]^b[i];dis[i][i]=1;}int x,y;while(scanf("%d%d",&x,&y),x||y){dis[y-1][x-1]=1;}int ss=gauss(dis,n,l,ans);if(ss==-1 ) printf("Oh,it's impossible~!!\n");else printf("%d\n",ss);}return 0;
}
總結
以上是生活随笔為你收集整理的poj 1830 开关问题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
