BZOJ1061: [Noi2008]志愿者招募 线性规划之--构造初始可行解

首要思路是构造辅助线性规划,若最优值为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;
}