#include <cstdio>
using namespace std;
#define varMax 100
#define eqMax 100
#define rMax eqMax+1
#define cMax varMax+eqMax+1
typedef long double dtype;
dtype table[rMax][cMax];
dtype solution[rMax];
int rId[rMax],cId[cMax];
char basic[cMax];
int N,M;
int Pivot(){
    int a,b;
    dtype c;
    a=b=0;
    for (int i=1;i<M;i++)if (basic[cId[i]]==0)if (table[0][i]<table[0][a])a=i;
    if (table[0][a]>0.0)return 0;
    for (int i=1;i<N;i++)
        if (table[i][a]>0.0 && solution[i]>0.0 || table[i][a]<0.0 && solution[i]<0.0){
           if (b==0)b=i;
           else if (solution[i]/table[i][a]<solution[b]/table[b][a])b=i;
        }
    if (b==0)return -1;
    basic[cId[a]]=1;basic[rId[b]]=0;
    rId[b]=cId[a];
    c=table[b][a];
    for (int i=0;i<M;i++)table[b][i]=table[b][i]/c;
    solution[b]=solution[b]/c;
    for (int i=0;i<N;i++)if (i!=b){
        c=table[i][a];
        for (int j=0;j<M;j++)table[i][j]=table[i][j]-c*table[b][j];
        solution[i]=solution[i]-c*solution[b];
    }
    return 1;
}
int LPresult;
void LP_core(){
     while ((LPresult=Pivot())==1);
}
float input[varMax][eqMax],rHand[eqMax],zrow[varMax];
int vc,ec;
void LP(){
     N=ec+1;M=ec+vc+1;
     for (int i=0;i<M;i++)table[0][i]=0.0;
     table[0][0]=1.0;
     for (int i=0;i<vc;i++)table[0][i+1]=-zrow[i];
     solution[0]=0.0;
     for (int i=1;i<N;i++){
         table[i][0]=0.0;
         for (int j=1;j<=vc;j++)table[i][j]=input[i-1][j-1];
         for (int j=vc+1;j<M;j++)table[i][j]=0.0;
         table[i][vc+i]=1.0;
         solution[i]=rHand[i-1];
     }
     for (int i=0;i<M;i++)cId[i]=i;
     rId[0]=0;
     for (int i=1;i<N;i++)basic[rId[i]=i+M-N]=1;
     LP_core();
}
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    vc=2;ec=2;
    zrow[0]=1;zrow[1]=1;
    rHand[0]=a;rHand[1]=b;
    input[0][0]=1.0;input[0][1]=0.0;
    input[1][0]=0.0;input[1][1]=1.0;
    LP();
    printf("%d\n",int(solution[0]));
    getchar();getchar();
    return 0;
}

• 杀鸡焉用牛刀 (7) fanhqme 2009-02-12 12:43:17