设为首页 加入收藏

TOP

poj 1830 开关问题 高斯消元
2015-07-24 06:38:53 来源: 作者: 【大 中 小】 浏览:47次
Tags：poj 1830 开关 问题 高斯

a1 a2 a3 1号灯

a1 a2 a3 2号灯

a1 a2 a3 3号灯

假设按2的时候影响1

那么就是第一行第二列为1，意思就是通过2号灯的变化可以影响1号灯

再有第i行第i列也为1，意思就是通过i号灯的变化可以影响i号灯

高斯消元求解方程，会得到r个解，剩下的n-r就是自由变元，其实意思就是可以随便取，比如0*x=0，那么x就是自由的了。

对于r个解，他们是按0下还是1下是已经固定了的，那么方案数就只有看自由变元里，由于自由变元取0或1都无所谓，所以就是2^k种

无解判断，只要看全为0的那些行，最后一个是不是非0就够了。

red-book的模板

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #define eps 1e-7 #define INF 0x7fffffff #define maxn 22222 using namespace std; double a[100][100]; double ans[100]; bool l[100]; int n; int gauss(){ int i,j,k,r=0; double tmp; for(i=0;i
            
             eps){ for(k=i;k<=n;k++) swap(a[j][k],a[r][k]); break; } if(fabs(a[r][i])
             
              eps){ 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=r;i
              
               eps)return -1; return 1<<(n-r); } int st[55]; int main() { int cas,x,y; int t; cin>>cas; while(cas--) { cin>>n; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) a[i][j]=0; for(int i=0;i
               
                >st[i]; for(int i=0;i
                
                 >t; a[i][n]=st[i]^t; a[i][i]=1; } while(cin>>x>>y,x||y) { a[y-1][x-1]=1; } x=gauss(); if(x==-1) puts("Oh,it's impossible~!!"); else cout<
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：C++单元测试--打桩测试 下一篇：[NOI2005] 维修数列

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: