hihoCoder #1195 : 高斯消元·一

2018-06-17 22:01:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

时间限制: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
样例输出
2
1
这坑爹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 }

 



    







标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷关押罪犯,并查集

下一篇:学生成绩管理系统