单纯形法的若干题目 BZOJ3112,3265,3550

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

#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剩下的两道题目也很类似.