hihoCoder #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 2
2 1 5
1 2 4样例输出21这坑爹oj没数据，害的我拍了以上午，题比较简单，高斯消元的模板题，注意eps要开double类型的
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<algorithm>
5 using namespace std;
6 const int MAXN=1001;
7 const double eps =1e-7;
8 typedef double Matrix[MAXN][MAXN] ;
9 inline void read(int &n)
10 {
11 char c=getchar();bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
14 }
15 int n,m;
16 Matrix a;
17 double t[MAXN];
18 void Gauss()
19 {
20 int r;
21 for(int i=1;i<=n;i++)// 枚举每一行
22 {
23 r=i;
24 for(int j=m;j>=i+1;j--)// 枚举后面的行
25 fabs(a[j][i])>fabs(a[r][i])?r=j:r=r;
26 if(r!=i) swap(a[r],a[i]);
27 if(r==i&&fabs(a[i][i])<eps) printf("Many solutions"),exit(0);
28
29 for(int j=i+1;j<=m;j++)// 行
30 {
31 for(int k=n+1;k>i;k--)// 列
32 a[j][k]-=(a[j][i]/a[i][i])*a[i][k];
33 a[j][i]=0;
34 }
35 }
36
37 for(int i=n,j;i<=m;i++)
38 {
39 for(j=1;j<=n;j++) if(fabs(a[i][j])>eps) break;
40 if(j==n+1&&fabs(a[i][n+1])>eps)
41 printf("No solutions\n"),exit(0);
42 }// 是否有解
43
44 for(int i=n;i>=1;i--)// 枚举行
45 {
46 for(int j=i+1;j<=n;j++)// 枚举列
47 a[i][n+1]-=a[i][j]*a[j][n+1];
48 a[i][n+1]/=a[i][i];
49 }
50 for(int i=1;i<=n;i++)
51 printf("%d\n",(int)(a[i][n+1]+0.5));
52 }
53 int main()
54 {
55 freopen("a.in","r",stdin);
56 freopen("c.out","w",stdout);
57 read(n);read(m);
58 for(int i=1;i<=m;i++)
59 for(int j=1;j<=n+1;j++)
60 scanf("%lf",&a[i][j]);
61 Gauss();
62
63 return 0;
64 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-08-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录