#include<iostream.h>
#include<math.h>
float matrix[100][100],x[100];
int a[100];
int m,n,s,type;
int indexe,indexl,indexg;
/////////////////////////////////
void jckxj()//基礎(chǔ)可行解
{
int i,j;
for(i=0;i<n;i++)
  for(j=0;j<s;j++)
   if(matrix[i][j]==1&&a[j]==1)
   {
    x[j]=matrix[i][s];
    j=s;
   }
   for(i=0;i<s;i++)
    if(a[i]==0)x[i]=0;
}

int rj()//基解矩陣
{
int i;
for(i=0;i<s;i++)
  if(fabs(matrix[n][i])>=0.000001)
   if(matrix[n][i]<0)return 0;
   return 1;
}
int Min()//求最小的
{
    int i,temp=0;
float min=matrix[n][0];
for(i=1;i<s;i++)
  if(min>matrix[n][i])
  {
   min=matrix[n][i];
   temp=i;
  }
  return temp;
}
/////////////////////////////////
void JustArtificial()//人工變量
{
int i;
for(i=m+indexe+indexl;i<s;i++)
  if(fabs(x[i])>=0.000001)
  {
   cout<<"NO Answer\n";
   return;
  }
}
/////////////////////
int Check(int in)//檢驗(yàn)
{
int i;
float maxl=-1;
for(i=0;i<n;i++)
  if(fabs(matrix[i][in])>=0.000001&&maxl<matrix[i][s]/matrix[i][in])
   maxl=matrix[i][s]/matrix[i][in];
  if(maxl<0)
   return 1;
  return 0;
}
int SearchOut(int *temp,int in)//出基變量
{
int i;
float min=10000;
for(i=0;i<n;i++)
  if(fabs(matrix[i][in])>=0.000001&&(matrix[i][s]/matrix[i][in]>=0)
   &&min>matrix[i][s]/matrix[i][in])
  {
   min=matrix[i][s]/matrix[i][in];
   *temp=i;
  }
  for(i=0;i<s;i++)
   if(a[i]=1&&matrix[*temp][i]==1)
    return i;
}
/////////////////////////////////
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)
  if(i!=in)
   matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
  matrix[temp][in]=1;
}
/////////////////////////////
void Be(int temp,int in)//初等變換
{
int i,j;
float c;
for(i=0;i<=n;i++)
{
  c=matrix[i][in]/matrix[temp][in];
  if(i!=temp)
   for(j=0;j<=s;j++)
    matrix[i][j]=matrix[i][j]-matrix[temp][j]*c;
}
}
//////////////////////////
void Achange(int in,int out)//出基入基轉(zhuǎn)換
{
int temp=a[in];
a[in]=a[out];
     a[out]=temp;
}
////////////////////////
void Print()
{
int i,j,k,temp=0;
for(i=0;i<n;i++)
{
  for(k=temp;k<s;k++)
   if(a[k]==1)
   {
    cout<<k;
    temp=k+1;
    k=s;
   }
   for(j=0;j<=s;j++)
    cout<<matrix[i][j];
   cout<<"\n";
}
cout<<"Rj";
for(j=0;j<=s;j++)
  cout<<matrix[n][j];
cout<<"\n";
}
////////////////////////
void InitPrint()
{
int i;
cout<<"X";
for(i=0;i<s;i++)
  cout<<i;
cout<<"b\n";
cout<<"  ";
cout<<"\n";
}
//////////////////
void Result()
{
int i;
cout<<"(";
for(i=0;i<s;i++)
  cout<<x[i];
cout<<")";
if(type==1)
  cout<<"Zmax="<<matrix[n][s];
else cout<<"Zmin="<<matrix[n][s];
}
//////////////////////
void PrintResult()
{
if(type==0)
  cout<<"the Minimal:"<<matrix[n][s];
else cout<<"theMaximum:"<<matrix[n][s];
}
////////////////////////////////
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并
{
int i,j;
for(i=0;i<n;i++)
{
  for(j=m;j<m+indexe;j++)
   if(nget[i][j-m]!=-1)matrix[i][j]=0;
   else matrix[i][j]=-1;
   for(j=m+indexe;j<m+indexe+indexl;j++)
    if(nlet[i][j-m-indexe]!=1)matrix[i][j]=0;
    else matrix[i][j]=1;
    for(j=m+indexe+indexl;j<s;j++)
     if(net[i][j-m-indexe-indexl]!=1)matrix[i][j]=0;
     else matrix[i][j]=1;
}
for(i=m;i<m+indexe+indexl;i++)
  matrix[n][i]=0;
for(i=m+indexe+indexl;i<s;i++)
  matrix[n][i]=100;
matrix[n][s]=0;
}

///////////////////////////
void ProcessA()//初始a[]
{
int i;
for(i=0;i<m+indexe;i++)
  a[i]=0;
for(i=m+indexe;i<s;i++)
  a[i]=1;
}

////////////////////////////////
void Input(float b[],int code[])
{
int i=0;int j=0;
cout<<"The equator variable and Restrictor\n";
cin>>m>>n;
for(i=0;i<n;i++)
{
  cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";
  cin>>b[i]>>code[i];
  cout<<"The 系數(shù)  \n";
  for(i=0;j<m;j++)
  cin>>matrix[i][j];
}
cout<<"the type 0:Min 1:max\n";
do{
  cin>>type;
  if(type!=0&&type!=1)
   cout<<"error,ReInput!\n";
}while(type!=0&&type!=1);
cout<<"the Z\n";
for(i=0;i<m;i++)
  cin>>matrix[n][i];
if(type==1)
  for(i=0;i<m;i++)
   matrix[n][i]=-matrix[n][i];
}                                            


//////////////////    
void Xartificial()//消去人工變量
{
int i,j,k;
if(indexg!=0)
{
  for(i=m+indexe+indexl;i<s;i++)
  {
   for(j=0;j<n;j++)
    if(matrix[j][i]==1)
    {
     for(k=0;k<=s;k++)
      matrix[n][k]=matrix[n][k]-matrix[j][k]*100;
     j=n;
    }
  }
}
}

////////////////////////////////////////////////
void Process(float c[][100],int row,int vol)
{
int i;
for(i=0;i<n;i++)
  if(i!=row)c[i][vol]=0;
}
//////////////////////
void Start(float b[],int code[])
{
int i;
float nget[100][100],nlet[100][100],net[100][100];
indexe=indexl=indexg=0;
for(i=0;i<n;i++)
{
  if(code[i]==0){nlet[i][indexl++]=1;Process(nlet,i,indexl-1);}
  if(code[i]==1){net[i][indexl++]=1;Process(net,i,indexg-1);}
  if(code[i]==2){
   net[i][indexg++]=1;
   nget[i][indexe++]=-1;
            Process(net,i,indexg-1);Process(nlet,i,indexe-1);
  }
}
s=indexe+indexl+indexg+m;
Merge(nget,nlet,net,b);
ProcessA();
InitPrint();
Xartificial();
}

void Simplix()//單純形法
{
int in,out,temp=0;
while(1)
{
  jckxj();
  Print();
        Result();
        if(!rj()) in=Min();
  else{
   if(indexg!=0)
    JustArtificial();
   PrintResult();
   return;
  }
  if(Check(in))
  {
   cout<<"No Delimition\n";
   return;
  }
  out=SearchOut(&temp,in);
  Mto(in,temp);
  Be(temp,in);
  Achange(in,out);
}
}

void main()
{
int code[100];//輸入符號(hào)標(biāo)記
float b[100];
Input(b,code);//初始化
Start(b,code);//標(biāo)準(zhǔn)化行
Simplix();
}