题目链接：https://vjudge.net/problem/UVA-10498

题意：n种食物m个人，已知每种食物的单价，每个人吃每种食物的愉快值，每个人的愉快值上限，求花钱买食物所花钱

的最大值

解法：

线性规划；可得标准形式，带入模版；

标准形式即由不等式构成的方程组，松弛形式即由等式构成的方程组；

等式转不等式，用既大于等于又小于等于表示；不等式转等式，用增加一个变量，新增变量大于0来表示；

#include <bits/stdc++.h>
using namespace std;

#define INF 1e10
#define EPS 1e-7
int n, m;
namespace Linear_Programming{
    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;
    while(~scanf("%d%d",&n,&m)){
        v = 0;
        for(int i=1; i<=n; i++) scanf("%lf",&c[i]);
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++) scanf("%lf", &A[i][j]);
            scanf("%lf", &b[i]);
        }
        double ans = Simplex();
        printf("Nasa can spend %.0f taka.\n", ceil(m*ans));
    }
    return 0;
}