如果有相应的OJ题目,欢迎同学们提供相应的链接

相关链接

• 所有模板的快速链接

简单的测试

None

代码模板

/*

 * TIME COMPLEXITY:O(n^3)

 * PARAMS:

 *      a       The responding matrix of equation set.

 *      n       number of unknown factor.

 *      l       l[] mean if it is the free unit.

 *      ans     answer of unknown factor.

 */

int solve(double a[][MAXN],bool l[],double ans[],const int& n){

    int res=0,r=0;

    for(int i=0;i<n;i++)

        l[i]=false;

    for(int i=0;i<n;i++){

        for(int j=r;j<n;j++)

            if(fabs(a[j][i])>EPS){  //Be sure current value larger than EPS.

                for(int k=i;k<=n;k++)

                    swap(a[j][k],a[r][k]);

                break;

            }

        if(fabs(a[r][i])<EPS){  //The value of every cell in current column smaller than EPS or 0.

            res++;

            continue;

        }

        //elimination

        for(int j=0;j<n;j++)

            if(j!=r && fabs(a[i][j])>EPS){

                double tmp=a[j][i]/a[r][i];

                for(int k=i;k<=n;k++)

                    a[j][k]-=tmp*a[r][k];

            }

        l[i]=true,++r;

    }

    /*

     * Here we got a new matrix,like this.

     * * * * * * *

     * 0 * * * * *

     * 0 0 * * * *

     * 0 0 0 * * *

     * 0 0 0 0 * *

     * 0 0 0 0 0 *

     *

     * Got ans.

     */

    for(int i=0;i<n;i++)

        if(l[i])

            for(int j=0;j<=n;j++)

                if(fabs(a[i][j])>0)

                    ans[i]=a[j][n]/a[j][i];

    return res;

}