随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.2.4 Feed Ratios (枚举+克莱姆法则)

其实就是解线性方程.

用克莱姆法则求解, 求解过程要判断是否是分数解或者负解。

Ax = k*B   枚举B, 从1到100.

/*
ID: lorelei3
TASK: ratios
LANG: C++
*/

#include <fstream>

using namespace std;

int A[4][4];
int B[4], b[4];
int x[4];
int D;

int det(){
    return    A[1][1]*(A[2][2]*A[3][3]-A[3][2]*A[2][3])-
            A[1][2]*(A[2][1]*A[3][3]-A[3][1]*A[2][3])+
            A[1][3]*(A[2][1]*A[3][2]-A[3][1]*A[2][2]);
}


int Cramer(){
    int i,j;
    int tmp[4];
    for(i=1; i<=3; ++i){

        for(j=1; j<=3; ++j){
            tmp[j] = A[j][i];
            A[j][i] = B[j];
        }

        int Di = det();

        for(j=1; j<=3; ++j)
            A[j][i] = tmp[j];

        if(Di%D != 0)
            return -1;

        x[i] = Di/D;

        if(x[i]<0)
            return -1;        
    }
    return 1;
}

int main(){
    int i,j,k;

    ifstream fin("ratios.in");
    ofstream fout("ratios.out");

    for(i=1; i<=3; ++i)
        fin>>b[i];

    for(i=1; i<=3; ++i)
        for(j=1; j<=3; ++j)
            fin>>A[j][i];

    D=det();
    
    for(k=1; k<=100; ++k){
        for(i=1; i<=3; ++i)
            B[i] = k*b[i];

        if(Cramer()==1){
            for(i=1; i<=3; ++i)
                fout<<x[i]<<" ";
            fout<<k<<endl;
            return 0;
        }
    }
    
    fout<<"NONE"<<endl;
    return 0;
}
posted on 2010-12-23 16:46 小阮 阅读(202) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮