#1195 : 高斯消元·一

时间限制:

10000ms

单点时限:

1000ms

内存限制:

256MB

描述

小Ho：喂不得了啦，那边便利店的薯片半价了!

小Hi：啥?!

小Ho：那边的便利店在打折促销啊。

小Hi：走走走，赶紧去看看=v=

于是小Hi和小Ho来到了便利店。

老板为了促销，推出了组合包的形式，将不同数量的各类商品打包成一个组合，顾客可以选择组合进行购买。比如2袋薯片，1听可乐的组合只要5元，而1袋薯片，2听可乐的组合只要4元。

通过询问老板，小Hi和小Ho知道：一共有N种不同的商品和M种不同的商品组合；每一个组合的价格等于组合内商品售价之和，一个组合内同一件商品不会超过10件。

小Hi：这样算下来的话，一听可乐就是1元，而一包薯片是2元。小Ho，如果你知道所有的组合情况，你能分别算出每一件商品单独的价格么？

小Ho：当然可以了，这样的小问题怎么能难到我呢？

   

 

输入

第1行：2个正整数，N,M。表示商品的数量N，组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行：N+1个非负整数，第i+1行第j列表示在第i个组合中，商品j的数量a[i][j]。第i+1行第N+1个数表示该组合的售价c[i]。0≤a[i][j]≤10, 0≤c[i]≤10^9

输出

若没有办法计算出每个商品单独的价格，输出"No solutions"

若可能存在多个不同的结果，输出"Many solutions"

若存在唯一可能的结果，输出N行，每行一个非负整数，第i行表示第i个商品单独的售价。数据保证如果存在唯一解，那么解一定恰好是非负整数解。

样例输入

2 22 1 51 2 4

样例输出

21 分析：高斯消元裸题，其实就是用矩阵解方程，学过线代都知道怎么算， 不过我学线代的时候不知道这个叫高斯消元=_=...... 注意有误差,用fabs(x)<1e-6判断x==0,我发现网上有几个代码是错的， 但竟然AC了=_=...

#include
           
            #include
            
             #include
             
              #include
              
               using namespace std;double a[1200][600],b[600];int flag=0;int N,M;//N个未知数,即M行N+1列 int Guass(){    for(int i=1,c=1;i<=N;i++)//i是列数,一个一个消去,c为行数     {
         //上三角         if(fabs(a[c][i])<1e-6)//第c行第i个为0         {
         //找出i+1到第M行中,第i个数不为0的行             int p=M;            for(;p>c;p--)            if(fabs(a[p][i])>1e-6) break;            if(p==c) continue;            else swap(a[c],a[p]);//交换c,p两行         }        //消去第c+1到第M行的第i个数         for(int k=c+1;k<=M;k++)        {            for(int j=i+1;j<=N+1;j++)            {                a[k][j]-=a[c][j]/a[c][i]*a[k][i];            }            a[k][i]=0;        }        c++;    }    /*for(int i=1;i<=M;i++)    {        for(int j=1;j<=N+1;j++) printf("%lf ",a[i][j]);        printf("\n");    }*/        //判断是否无解或多解     for(int k=M;k>0;k--)    {        int j=1;        for(;j<=N;j++)        if(fabs(a[k][j])>1e-6) break;        if(j>N&&fabs(a[k][N+1])>1e-6) return -1;//无解         else if(j<=N&&k