1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <cfloat>
#include <algorithm>
const int MAXN = 1005;
const int MAXM = 10005;
const double EPS = 1e-7;
struct {
double A[MAXM][MAXN], b[MAXM], c[MAXN], v;
int n, m;
void pivot(int l, int e) {
b[l] /= A[l][e];
for (int i = 1; i <= n; i++) if (i != e) A[l][i] /= A[l][e];
A[l][e] = 1 / A[l][e];
for (int i = 1; i <= m; i++) {
if (i != l && abs(A[i][e]) > EPS) {
b[i] -= A[i][e] * b[l];
for (int j = 1; j <= n; j++) if (j != e) A[i][j] -= A[i][e] * A[l][j];
A[i][e] = -A[i][e] * A[l][e];
}
}
v += c[e] * b[l];
for (int i = 1; i <= n; i++) if (i != e) c[i] -= c[e] * A[l][i];
c[e] = -c[e] * A[l][e];
}
double operator()(int n, int m) {
this->n = n;
this->m = m;
while (true) {
int i;
for (i = 1; i <= n; i++) if (c[i] > EPS) break;
int e = i;
if (e == n + 1) return v;
double temp = DBL_MAX;
int l;
for (i = 1; i <= m; i++) if (A[i][e] > EPS && b[i] / A[i][e] < temp) temp = b[i] / A[i][e], l = i;
if (temp == DBL_MAX) return DBL_MAX;
pivot(l, e);
}
}
} lp;
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lf", &lp.c[i]);
for (int i = 1; i <= m; i++) {
int s, t, c;
scanf("%d %d %d", &s, &t, &c);
for (int j = s; j <= t; j++) lp.A[i][j] = 1;
lp.b[i] = c;
}
printf("%dn", (int) (lp(n, m) + 0.5));
return 0;
}
|
近期评论