首要思路是构造辅助线性规划,若最优值为0则删除辅助变量得到存在初始可行解线性规划.

具体看代码吧.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define inf 0x3f3f3f3f
struct Linear_Programming{
    static const int N=10010;
    static const int M=1010;
    int n,m,A[M][N],b[M],c[N],v,B[M],nB[N];
    int _c[N],_v,Bins[N+M],nBins[N+M],_nB[N];
    inline void pivot(int l,int e){
        int i,j;
        for(i=1;i<=n;++i)
            if(i!=e)
                A[l][i]/=A[l][e];
        b[l]/=A[l][e];
        A[l][e]=1/A[l][e];
        for(i=1;i<=m;++i)
            if(i!=l&&A[i][e]!=0){
                for(j=1;j<=n;++j)
                    if(j!=e)
                        A[i][j]-=A[i][e]*A[l][j];
                b[i]-=A[i][e]*b[l];
                A[i][e]*=-A[l][e];
            }
        for(i=1;i<=n;++i)
            if(i!=e)
                c[i]-=c[e]*A[l][i];
        v+=c[e]*b[l];
        c[e]*=-A[l][e];
        swap(B[l],nB[e]);
    }
    inline int Simplex(){
        int i,j,l,e,lim;
        while(1){
            for(e=0,i=1;i<=n;++i)
                if(c[i]>0){
                    e=i;
                    break;
                }
            if(!e)
                return v;
            for(lim=inf,i=1;i<=m;++i)
                if(A[i][e]>0&&lim>b[i]/A[i][e]){
                    l=i;
                    lim=b[i]/A[i][e];
                }
            if(lim==inf)
                return inf;
            pivot(l,e);
        }
    }
    inline bool init(){
        int i,j,l,e,min_b=inf;
        for(l=0,i=1;i<=m;++i)
            if(b[i]<min_b){
                min_b=b[i];
                l=i;
            }
        if(min_b>=0)
            return 1;
        nB[++n]=0;
        memcpy(_c,c,sizeof c);
        _v=v;
        memcpy(_nB,nB,sizeof nB);
        memset(c,0,sizeof c);
        v=0;
        c[n]=-1;
        for(i=1;i<=m;++i)
            A[i][n]=-1;
        pivot(l,n);
        if(Simplex()<0)
            return 0;
        else{
            for(i=1;i<=m;++i)
                if(B[i]==0){
                    for(j=1;j<=n;++j){
                        if(A[i][j]!=0)
                            pivot(i,j);
                        break;
                    }
                }
            for(i=1;i<=n;++i)
                if(nB[i]==0)
                    e=i;
            --n;
            for(i=e;i<=n;++i)
                nB[i]=nB[i+1];
            for(i=1;i<=m;++i)
                for(j=e;j<=n;++j)
                    A[i][j]=A[i][j+1];
            for(i=1;i<=n;++i)
                nBins[nB[i]]=i;
            for(i=1;i<=m;++i)
                Bins[B[i]]=i;
            memset(c,0,sizeof c);
            v=_v;
            for(i=1;i<=n;++i){
                if(nBins[_nB[i]])
                    c[nBins[_nB[i]]]+=_c[i];
                else{
                    v+=_c[i]*b[Bins[_nB[i]]];
                    for(j=1;j<=n;++j)
                        c[j]-=_c[i]*A[Bins[_nB[i]]][j];
                }
            }
            return 1;
        }
    }
}g;
 
int main(){
    int tim,typ;
    cin>>tim>>typ;
    int i,j;
    for(i=1;i<=tim;++i){
        scanf("%d",&g.b[i]);
        g.b[i]=-g.b[i];
    }
    int s,t,c;
    for(i=1;i<=typ;++i){
        scanf("%d%d%d",&s,&t,&c);
        for(j=s;j<=t;++j)
            g.A[j][i]=-1;
        g.c[i]=-c;
    }
    g.n=typ;
    g.m=tim;
    for(i=1;i<=g.n;++i)
        g.nB[i]=i;
    for(i=1;i<=g.m;++i)
        g.B[i]=g.n+i;
    g.init();
    cout<<-g.Simplex()<<endl;
    return 0;
}

利用一下对偶原理建模什么的都非常裸,就放一下代码吧.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define INF ~0U>>1
 
struct Solver{
    static const int N=10010;//变量个数
    static const int M=1010;//限制个数
    int n,m;
    int B[M];//基变量集合
    int NB[N];//非基变量集合
    f2 c[N],v;//目标函数的各项系数以及常数
    f2 A[M][N],b[N];//限制的系数
     
    Solver(){}
    Solver(int _n,int _m):n(_n),m(_m){}
     
    void debug(){
        puts("Function");
        printf("Maximize ");
        for(int i=1;i<=n;++i){
            if(i>1)putchar('+');
            printf("%.2lfx_%d",c[i],NB[i]);
        }
        printf("+%.2lf\n",v);
         
        puts("Limits");
        for(int i=1;i<=m;++i){
            printf("x_%d",B[i]);
            for(int j=1;j<=n;++j)printf("+%.2lfx_%d",A[i][j],NB[j]);
            printf("<=%.2lf\n",b[i]);
        }
    }
     
    inline void pivot(int l,int e){//转轴操作,将第l个基变量与第e个非基变量进行交换
        int i,j,k;
         
        //更改第l个限制,得到x_e与x_l的关系式
        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];
         
        //将x_e带入,更改剩余的所有限制
        for(i=1;i<=m;++i)if(i!=l&&A[i][e]!=0){
            b[i]-=b[l]*A[i][e];
            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];
        swap(B[l],NB[e]);
    }
    inline f2 solve(){//得到线性规划的最优解,或者返回无界区域
        int i,j,l,e,lim;
         
        while(1){
            for(e=0,i=1;i<=n;++i)if(c[i]>0){e=i;break;}//寻找最小标号的可行非基变量
            if(e==0)return v;//如果不存在这样的非基变量,则已经是最优解,直接返回
             
            //寻找最紧的上界
            for(lim=INF,i=1;i<=m;++i)if(A[i][e]>0&&lim>b[i]/A[i][e])l=i,lim=b[i]/A[i][e];
            if(lim==INF)return INF;//没有限制,返回无界区域
            else pivot(l,e);//否则进行转轴操作
        }
    }
}Complex;
 
void output(){Complex.debug();}
 
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    register int i,j;
     
    Complex.n=m,Complex.m=n;
    int x;
    for(i=1;i<=n;++i)scanf("%d",&x),Complex.b[i]=x;
     
    int l,r;
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&l,&r,&x);
        for(j=l;j<=r;++j)Complex.A[j][i]=1;
        Complex.c[i]=x;
    }
     
    for(i=1;i<=Complex.n;++i)Complex.NB[i]=i;
    for(i=1;i<=Complex.m;++i)Complex.B[i]=Complex.n+i;
     
    //Complex.debug();
     
    printf("%d",(int)Complex.solve());
 
    return 0;
}

233剩下的两道题目也很类似.