UVA 10498 Happiness（线性规划-单纯形）

浏览数：33 / 时间：2015年06月11日

Description

Prof. Kaykobad has given Nasa the duty of buying some food for the ACM contestents. Nasa decided to buy n different items. He then asked each of the mcontestents how much of each item they want to eat. They could not give any logical answer, they only want as much as they wish! Nasa knows quite well that they would only waste their food if they get as much as they want. He was determined not to let that happen.

So he tactfully found out from each of the contestents how much ‘happiness‘ one gets from each piece of each item and what is the ‘total happiness‘ over which one wastes food. It may be the case that someone gets ‘zero‘ ‘happiness‘ on some item(s). He decided that he would never let anyone have such amount of food that exceeds his ‘total happiness‘. He planned that he would give someone even a fraction of a piece of item, but never give anyone more than he needed!

He also decided that each would get exactly the same amount of each item so that no one can complain against him.

After planning all these, he finally realized that he has an infinite amount of money and hence, he would spend as much money as he can.

Input

Input contains data collected by Nasa on several days.

For each day,

The first line contains the integers n(3<=n<=20) and m(3<=m<=20).

The next line contains n real numbers, the per unit price of each item.

Each of the next m lines contain data (n+1 real numbers) of each contestents: first n are ‘happiness‘ got from each item and the last one is the ‘total happiness‘.

Output

For the data collected in each day print in a single line the maximum amount of money Nasa can spend in taka rounded up to nearest integer. You can assume that there will be no such input which may cause serious floating point errors.

题目大意：某人要买套餐给m个人吃，每个人吃的套餐必须都是一样的。套餐由n种食品组成，每种食品的单位价格是已知的。由于口味不同，每个人每得到一单位的某种食品获得的满足度可能不一样，这些也是已知的。每个人满足度是有上限的，上限已知。求在不超过任何人的满足度上限的条件下，此人最多能花多少钱。（某种食品可以买实数单位）

思路：线性规划的模板题。可以参考IOI国家集训队论文《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》（上面的题目大意也是来自这里……）或者《算法导论》。

代码（32MS）：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 const double EPS = 1e-10;
 9 const int MAXN = 55;
10 const int INF = 0x3fff3fff;
11 
12 inline int sgn(double x) {
13     return (x > EPS) - (x < -EPS);
14 }
15 
16 double A[MAXN][MAXN], tA[MAXN][MAXN];
17 double b[MAXN], tb[MAXN], c[MAXN], tc[MAXN];
18 int N[MAXN], B[MAXN];
19 int n, m;
20 double v;
21 
22 bool init() {
23     N[0] = B[0] = v = 0;
24     for(int i = 1; i <= n; ++i) N[++N[0]] = i;
25     for(int i = 1; i <= m; ++i) B[++B[0]] = n + i;
26     return true;
27 }
28 
29 void pivot(int l, int e) {
30     tb[e] = b[l] / A[l][e];
31     tA[e][l] = 1.0 / A[l][e];
32     for(int i = 1; i <= N[0]; ++i)
33         if(N[i] != e) tA[e][N[i]] = A[l][N[i]] / A[l][e];
34     for(int i = 1; i <= B[0]; ++i) {
35         tb[B[i]] = b[B[i]] - A[B[i]][e] * tb[e];
36         tA[B[i]][l] = -A[B[i]][e] * tA[e][l];
37         for(int j = 1; j <= N[0]; ++j)
38             if(N[j] != e) tA[B[i]][N[j]] = A[B[i]][N[j]] - tA[e][N[j]] * A[B[i]][e];
39     }
40     v += tb[e] * c[e];
41     tc[l] = -tA[e][l] * c[e];
42     for(int i = 1; i <= N[0]; ++i)
43         if(N[i] != e) tc[N[i]] = c[N[i]] - tA[e][N[i]] * c[e];
44     for(int i = 1; i <= N[0]; ++i) if(N[i] == e) N[i] = l;
45     for(int i = 1; i <= B[0]; ++i) if(B[i] == l) B[i] = e;
46     for(int i = 1; i <= B[0]; ++i) {
47         for(int j = 1; j <= N[0]; ++j)
48             A[B[i]][N[j]] = tA[B[i]][N[j]];
49         b[B[i]] = tb[B[i]];
50     }
51     for(int i = 1; i <= N[0]; ++i) c[N[i]] = tc[N[i]];
52 }
53 
54 bool simplex() {
55     while(true) {
56         int e = MAXN;
57         for(int i = 1; i <= N[0]; ++i)
58             if(c[N[i]] > EPS && N[i] < e) e = N[i];
59         if(e == MAXN) break;
60         double delta = -1;
61         int l = MAXN;
62         for(int i = 1; i <= B[0]; ++i) {
63             if(sgn(A[B[i]][e]) > 0) {
64                 double tmp = b[B[i]] / A[B[i]][e];
65                 if(delta == -1 || sgn(tmp - delta) < 0 || (sgn(tmp - delta) == 0 && B[i] < l)) {
66                     delta = tmp;
67                     l = B[i];
68                 }
69             }
70         }
71         if(l == MAXN) return false;
72         pivot(l, e);
73     }
74     return true;
75 }
76 
77 int main() {
78     while(scanf("%d%d", &n, &m) != EOF) {
79         for(int i = 1; i <= n; ++i) scanf("%lf", &c[i]);
80         for(int i = 1; i <= m; ++i) {
81             for(int j = 1; j <= n; ++j) scanf("%lf", &A[n + i][j]);
82             scanf("%lf", &b[n + i]);
83         }
84         init();
85         simplex();
86         printf("Nasa can spend %d taka.\n", (int)ceil(v * m));
87     }
88 }