bzoj 1061 [Noi2008]志願者招募 單純形算法

Description

　　申奧成功後，布布經過不懈努力，終于成為奧組委下屬公司人力資源部門的主管。布布剛上任就遇到了一個難

題：為即将啟動的奧運新項目招募一批短期志願者。經過估算，這個項目需要N 天才能完成，其中第i 天至少需要

Ai 個人。 布布通過了解得知，一共有M 類志願者可以招募。其中第i 類可以從第Si 天工作到第Ti 天，招募費用

是每人Ci 元。新官上任三把火，為了出色地完成自己的工作，布布希望用盡量少的費用招募足夠的志願者，但這

并不是他的特長！于是布布找到了你，希望你幫他設計一種最優的招募方案。

Input

　　第一行包含兩個整數N, M，表示完成項目的天數和可以招募的志願者的種類。 接下來的一行中包含N 個非負

整數，表示每天至少需要的志願者人數。 接下來的M 行中每行包含三個整數Si, Ti, Ci，含義如上文所述。為了

友善起見，我們可以認為每類志願者的數量都是無限多的。

Output

　　僅包含一個整數，表示你所設計的最優方案的總費用。

Sample Input

3 3

2 3 4

1 2 2

2 3 5

3 3 2

Sample Output

14

HINT

1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，題目中其他所涉及的資料均 不超過2^31-1。

似乎是裸的線性規劃……

然而一開始不會啊QAQ

先想了個比較明顯的……假如第i個志願者在第j天工作，

那麼系數矩陣a[j][i]=1，然後矩陣裡對應一下……

于是樣例就是這樣的一個線性規劃：

minimize:2∗x1+5∗x2+2∗x3satisfy:x1∗1+x2∗0+x3∗0>=2x1∗1+x2∗1+x3∗0>=3x1∗0+x2∗1+x3∗1>=4

結果……我靠既不是求max又不是小于等于！

幸好記得以前看到過這個的對偶問題……好像怎樣弄一下就直接好了？

……似乎是把系數矩陣帶着要求的值和答案的系數，一起翻轉一下？

這個翻轉……就是YY一下左上右下反過來（唔……）

那麼樣例就變成了：

maximize:2∗x1+3∗x2+4∗x3satisfy:x1∗1+x2∗1+x3∗0<=2x1∗0+x2∗1+x3∗1<=5x1∗0+x2∗0+x3∗1<=2

然後就對啦。。後來知道了這個東西叫做矩陣的轉置。。

轉置是啥……問度娘吧！舉個簡單的例子，就是：

⎡⎣⎢123456⎤⎦⎥T=[142536]

看上去就這麼解決了，但是我們忘記了一個很重要的東西？……

沒錯……這題裡的值得是整數啊！這不是整數線性規劃嗎？NP？

我當時就糾結了很久。。這樣就不能用單純形了啊。。

然後就各種百度……終于發現了這麼一個東西叫做“幺模矩陣”

還有一句話“系數矩陣全為0,1或者-1的，一定有至少一組最優解全為整數”

……似乎還有行列式的說法更正式一點……

數學這東西我真的不好啊QAQ

線性規劃第二題1A了（除掉手殘數組開反2次）很開心=v=

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double 
    eps=1e-8;
int n,m;
double a[10005][1005];
void pivot(int l,int e){
    double x=a[l][e];a[l][e]=1.0;
    for (int i=0;i<=m;i++) a[l][i]/=x;
    for (int i=0;i<=n;i++)
        if (i!=l && fabs(a[i][e])>eps){
            x=a[i][e],a[i][e]=0.0;
            for (int j=0;j<=m;j++) a[i][j]-=x*a[l][j];
        }
}
double Simplex(){
    while (1){
        int x=0,y=0;
        for (int i=1;i<=m;i++)
            if (a[0][i]>eps){y=i;break;}
        if (!y) break;
        double t=1e15;
        for (int i=1;i<=n;i++)
            if (a[i][y]>eps && a[i][0]/a[i][y]<t)
                t=a[i][0]/a[i][y],x=i;
        if (!x) return -1;
        pivot(x,y);
    }
    return -a[0][0];
}
int main(){
    scanf("%d%d",&m,&n);
    for (int i=1;i<=m;i++) scanf("%lf",&a[0][i]);
    int x,y;
    for (int i=1;i<=n;i++){
        scanf("%d%d%lf",&x,&y,&a[i][0]);
        for (int j=x;j<=y;j++) a[i][j]=1.0;
    }
    printf("%.0lf\n",Simplex());
    return 0;
}