[NOI2008]志愿者招募

第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。
接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。
接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

C++ 解法, 执行用时: 257ms, 内存消耗: 78072K, 提交时间: 2021-06-06 14:38:07

#include <bits/stdc++.h>
using namespace std;
#define INF 1e10
#define EPS 1e-7
int n, m;

    double A[10100][1010],b[10100],c[1010],v;
    void Pivot(int l,int e)
    {
        int i,j;

        b[l]/=A[l][e];
        for(i=1;i<=n;i++)
            if(i!=e)
                A[l][i]/=A[l][e];
        A[l][e]=1/A[l][e];

        for(i=1;i<=m;i++)
            if(i!=l&&fabs(A[i][e])>EPS)
            {
                b[i]-=A[i][e]*b[l];
                for(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(i=1;i<=n;i++)
            if(i!=e)
                c[i]-=c[e]*A[l][i];
        c[e]=-c[e]*A[l][e];
    }
    double Simplex()
    {
        int i,l,e;
        while(1)
        {
            for(i=1;i<=n;i++)
                if(c[i]>EPS)
                    break;
            if((e=i)==n+1)
                return v;
            double temp=INF;
            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==INF) return INF;
            Pivot(l,e);
        }
    }


int main(){
    //using namespace Linear_Programming;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lf", &c[i]);
    for(int i = 1; i <= m; i++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        for(int j = x; j <= y; j++){
            A[i][j] = 1;
        }
        b[i] = z;
    }
    double ans = Simplex();
    printf("%d\n", (int)(ans + 0.5));
    return 0;
}

详情