模板：线性规划

 1 //数组开不下时勿用
 2 const int maxn=110;
 3 const double eps=1e-10;
 4 double a[maxn][maxn];
 5 double b[maxn],c[maxn],v;
 6 int N[maxn],B[maxn],n,m;
 7 
 8 int SGN(double x){
 9     return (x>eps)-(x<-eps);
10 }
11 
12 void Init(){
13     N[0]=B[0]=0;v=0.0;
14     for(int i=1;i<=n;i++)N[++N[0]]=i;
15     for(int i=1;i<=m;i++)B[++B[0]]=n+i;
16 }
17 
18 void Pivot(int l,int e){
19     b[e]=b[l]/a[l][e];
20     a[e][l]=1.0/a[l][e];
21     for(int i=1;i<=N[0];i++)
22         if(N[i]!=e)a[e][N[i]]=a[l][N[i]]/a[l][e];
23     
24     for(int i=1;i<=B[0];i++)
25         if(B[i]!=l){
26             b[B[i]]-=a[B[i]][e]*b[e];
27             a[B[i]][l]=-a[B[i]][e]*a[e][l];
28             for(int j=1;j<=N[0];j++)
29                 if(N[j]!=e)a[B[i]][N[j]]-=a[B[i]][e]*a[e][N[j]];
30         }    
31         
32     v+=b[e]*c[e];
33     c[l]=-c[e]*a[e][l];
34     for(int i=1;i<=N[0];i++)
35         if(N[i]!=e)c[N[i]]-=c[e]*a[e][N[i]];
36     for(int i=1;i<=N[0];i++)if(N[i]==e)N[i]=l;
37     for(int i=1;i<=B[0];i++)if(B[i]==l)B[i]=e;
38 }
39 
40 bool Simplex(){
41     while(true){
42         double lam=-1;
43         int e=maxn,l=maxn;
44         for(int i=1;i<=N[0];i++)
45             if(SGN(c[N[i]])>0&&e>N[i])
46                 e=N[i];
47         if(e==maxn)break;
48         
49         for(int i=1;i<=B[0];i++)
50             if(SGN(a[B[i]][e])>0){
51                 double tmp=b[B[i]]/a[B[i]][e];
52                 if(lam==-1||SGN(tmp-lam)<0||SGN(tmp-lam)==0&&l>B[i])
53                     lam=tmp,l=B[i];
54             }
55         if(l==maxn)return false;
56         Pivot(l,e);    
57     }
58     return true;
59 }

　　这个是整数规划的模板，总能对，但正确性不显然。

 1 const int maxr=1010;
 2 const int maxc=10010;
 3 
 4 int n,m,nxt[maxc];
 5 int a[maxr][maxc];
 6 
 7 void Pivot(int l,int e){
 8     int pre=maxc-1;
 9     for(int i=0;i<=n;i++)
10         if(a[l][i]!=0){nxt[pre]=i;pre=i;}
11     nxt[pre]=-1;
12             
13     for(int i=0,t;i<=m;i++)
14         if(i!=l&&(t=a[i][e])){
15             a[i][e]=0;
16             for(int j=nxt[maxc-1];j!=-1;j=nxt[j])
17                 a[i][j]+=t*a[l][j];
18         }
19 }
20 
21 void Simplex(){
22     while(true){
23         int e=0,l=0;
24         for(int i=1;i<=n;i++)
25             if(a[0][i]>0){e=i;break;}
26         if(e==0)break;        
27         for(int i=1;i<=m;i++)
28             if(a[i][e]<0&&(!l||a[l][0]>a[i][0]))
29                 {l=i;}
30         
31         Pivot(l,e);    
32     }
33 }