时间限制: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
View Code/** 题意：如题 做法：高斯消元 因为浮点数 WA了很多次 **/ #include <iostream> #include <algorithm> #include <cmath> #include <string.h> #include <stdio.h> #include <queue> using namespace std; const int maxn = 1010; double a[maxn][maxn]; double x[maxn]; int guess(int row, int col) ///col 列 row 行 { for(int i = 1; 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-7) { return -1; } if(r != i) { swap(a[r], a[i]); } for(int j = i + 1; j <= row; j++) { for(int k = col; k > i; k--) { a[j][k] -= a[j][i] / a[i][i] * a[i][k]; } a[j][i] = 0; } } int j; for(int i = col - 1, j; i <= row; i++) { for(j = 1; j < col; j++) if(fabs(a[i][j]) > 1e-6) { break; } if(j == col && fabs(a[i][col]) > 1e-6) { return 0; } }///col 列 row 行 for(int i = col - 1; i > 0; i--) { for(int j = i + 1; j < col; j++) { a[i][col] -= a[i][j] * x[j]; } x[i] = a[i][col] / a[i][i]; } return 1; } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++) { for(int j = 1; j <= n + 1; j++) { scanf("%lf", &a[i][j]); } } int ans = guess(m, n + 1); if(ans == -1) { puts("Many solutions"); } else if(ans == 0) { puts("No solutions"); } else { for(int i = 1; i <= n; i++) { printf("%d ", (int)(x[i] + 0.5)); } } return 0; }
