hihoCoder #1195 高斯消元·一

题意:便利店老板为了促销,推出了组合包的形式,将不同数量的各类商品打包成一个组合。比如2袋薯片,1听可乐的组合只要5元,而1袋薯片,2听可乐的组合只要4元。通过询问老板知道:一共有N种不同的商品和M种不同的商品组合;每一个组合的价格等于组合内商品售价之和,一个组合内同一件商品不会超过10件。

思路:高斯消元!精度的坑啊!一直错在90分!!!终于AC了,很多需要注意的地方!!

 #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=; double a[N][N];
double t[N]; //临时行
double value[N]; //临时行 int Gaussian_elimination(int row,int col)
{
//计算上三角
for(int i=; i<col; i++) //列
{
int r=i;
for(int j=row; j>i; j--)
if( fabs(a[j][i])>fabs(a[r][i]) )
r=j;
if(r==i && fabs(a[i][i])<1e-) return -; //注意点1:精度
if(r!=i) swap(a[r], a[i]); for( int j=i+; j<=row; j++)
{
for(int k=col; k>i; k--) //注意点2:反向
a[j][k]-= a[j][i]/a[i][i]*a[i][k];
a[j][i]=; //注意点3:必须置0
}
} //检查是否有解
for(int i=col-,j; i<=row; i++)
{
for(j=; j<col; j++) if(fabs(a[i][j])>1e-) break;
if(j==col && fabs(a[i][col])>1e- ) return ; //无解,左边系数全0,右边值不为0。反过来是可以的,因为可能有东西不用钱呢?
} for(int i=col-; i>; i--) //从正方形最后一行开始往上。
{
for(int j=i+; j<col; j++) //消掉i+1~col-1
a[i][col]-=a[i][j]*t[j];
t[i]=a[i][col]/a[i][i]; //答案
}
return ;
} int main()
{
freopen("input.txt", "r", stdin);
int m, n; scanf("%d%d",&n,&m);
for(int i=; i<=m; i++)
for(int j=; j<=n+; j++)
scanf("%lf", &a[i][j]); //a[][n+1]存价格
int ans=Gaussian_elimination(m, n+);
if(ans==-) puts("Many solutions");
else if(ans==) puts("No solutions");
else
{
for(int i=; i<=n; i++)
printf("%d\n", (int)(t[i]+0.5));
}
return ;
}

AC代码

上一篇:ubuntu安装QQ目前最完善的方法!(亲测,成功)


下一篇:hihoCoder#1196 : 高斯消元·二(开关灯问题)