程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1830 開關問題高斯消元

poj 1830 開關問題高斯消元

編輯：C++入門知識

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;ieps){
                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;ieps)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<