入门题目 ：bzoj 3112（zjoi 2013 防守战线） 线性规划+网络流
博客1 重点
博客2 重点

题目描述：

战线可以看作一个长度为n 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第i 号位置上建一座塔有Ci 的花费，且一个位置可以建任意多的塔，费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm]，在第i 个区间的范围内要建至少Di 座塔。求最少花费。

https://blog.csdn.net/SmallSXJ/article/details/73292523

#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const double eps=1e-6;
int n,m;
double c[10005],b[1005],cof[1005][10005];
void pivot(int in,int out,double &res){
    b[out]/=cof[out][in];
    for(int i=1;i<=n;i++) if(i!=in) cof[out][i]/=cof[out][in];
    cof[out][in]=1/cof[out][in];
    for(int i=1;i<=m;i++) if(i!=out&&fabs(cof[i][in])>eps){
        for(int j=1;j<=n;j++) if(j!=in) cof[i][j]-=cof[i][in]*cof[out][j];
        b[i]-=cof[i][in]*b[out];
        cof[i][in]=-cof[i][in]*cof[out][in];
    }
    res+=c[in]*b[out];
    for(int i=1;i<=n;i++) if(i!=in) c[i]-=cof[out][i]*c[in];
    c[in]=-c[in]*cof[out][in];
}   
double simplex(){
    double res=0;
    while(1){
        int in,out;
        for(in=1;in<=n;in++) if(c[in]>eps) break;
        if(in==n+1) break;
        double tmp=inf;
        for(int i=1;i<=m;i++) if(cof[i][in]>eps&&b[i]/cof[i][in]<tmp)
            tmp=b[i]/cof[i][in],out=i;
        if(tmp==inf) return inf;
        pivot(in,out,res);
    }
    return res;
}
int main(){
    freopen("data.in","r",stdin);//
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        scanf("%lf",&b[i]);
    }
    for(int i=1;i<=n;i++){
        int l,r;
        scanf("%d%d%lf",&l,&r,&c[i]);
        for(int j=l;j<=r;j++) cof[j][i]=1;
    }
    printf("%d\n",(int)(simplex()+0.5));
    return 0;
}

模板链接：
https://blog.csdn.net/hdu2014/article/details/51124340
https://github.com/sxysxy/math/blob/master/simplex/simplex.c
原理讲解：
https://blog.csdn.net/qq_36558948/article/details/80640768
http://www.cnblogs.com/zzqsblog/p/5457091.html
https://blog.csdn.net/u013632138/article/details/53609635

CCPC-final
http://www.voidcn.com/article/p-enkpvtgs-brm.html
一个比较好用的模板
https://blog.csdn.net/nike0good/article/details/78798436
https://blog.csdn.net/nike0good/article/category/7344434

//输入 标准型 线性规划，输出目标函数最优解
//输入格式:
/*
第一行两个整数n, m，表示n个自变量，m个约束
第二行n个正数，表示目标函数自变量前的系数
接下来m行，每行n+1个整数
前n个正数描述了这个约束的自变量前的系数，最后一个正数描述了这个约束 <=号 右边的数值
例:
输入(讲义里面讲单纯形法时用的例子):
3 3
3 1 2
1 1 3 30
2 2 5 24
4 1 2 36
输出:
28.00000000
*/

#include<bits/stdc++.h>
using namespace std;
const int Maxn=110,Maxm=59;
class Simplex{
    /* 功能： 接受有n个约束，m个基本变量的方程组a[0~n][0~m] a[0][]存放需要最大化的目标函数，a[][0]存放常数 Base[]存放基本变量的id,初始为1~m Rest[]存放松弛变量的id,初始为m+1~m+n 返回此线性规划的最小值ans 要求方案的话，Base[]中的变量值为0,Rest[]中的变量值为相应行的[0] 如果solve 返回1,说明运行正常ans是它的最大值 返回0,说明无可行解 返回-1,说明解没有最大值 测试： m=2,n=3 double a[4][3]={ {0,1,3}, {8,-1,1}, {-3,1,1}, {2,1,-4} }; solve=1,ans=64/3; 注意ac不了可能是eps的问题 */
    public:
        static const double Inf;
        static const double eps;
    int n,m;
    double a[Maxn][Maxm];
    int Base[Maxm],Rest[Maxn];
    double val[Maxm];
    double ans;
    void pt(){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++)printf("%.2f ",a[i][j]);
            puts("");
        }
    }
    void pivot(int x,int y){//将第x个非基本变量和第y个基本变量调换
        swap(Rest[x],Base[y]);
        double tmp=-1./a[x][y];
        a[x][y]=-1.;
        for(int j=0;j<=m;j++)a[x][j]*=tmp;
        for(int i=0;i<=n;i++){
            if(i==x||fabs(a[i][y])<eps)continue;
            tmp=a[i][y];
            a[i][y]=0;
            for(int j=0;j<=m;j++)a[i][j]+=tmp*a[x][j];
        }
    }
    bool opt(){
        while(1){
            int csi=0;
            for(int i=1;i<=m;i++)if(a[0][i]>eps&&(!csi||Base[i]<Base[csi]))csi=i;
            if(!csi)break;
            int csj=0;
            double cur;
            for(int j=1;j<=n;j++){
                if(a[j][csi]>-eps)continue;
                double tmp=-a[j][0]/a[j][csi];
                if(!csj||tmp+eps<cur||(fabs(tmp-cur)<eps&&Rest[j]<Rest[csj]))csj=j,cur=tmp;
            }
            if(!csj)return 0;
            pivot(csj,csi);
        }
        ans=a[0][0];
        return 1;
    }
    bool init(){
        ans=0;
        for(int i=1;i<=m;i++)Base[i]=i;
        for(int i=1;i<=n;i++)Rest[i]=m+i;
        int cs=1;
        for(int i=2;i<=n;i++)if(a[i][0]<a[cs][0])cs=i;
        if(a[cs][0]>=-eps)return 1;
        static double tmp[Maxm];
        for(int i=0;i<=m;i++)tmp[i]=a[0][i],a[0][i]=0;
        for(int i=1;i<=n;i++)a[i][m+1]=1.;
        a[0][m+1]=-1.;Base[m+1]=m+n+1;
        pivot(cs,++m);
        opt();
        m--;
        if(a[0][0]<-eps)return 0;
        cs=-1;
        for(int i=1;i<=n;i++){
            if(Rest[i]>m+n){
                cs=i;
                break;
            }
        }
        if(cs>=1){
            int nxt=-1;
            m++;
            for(int i=1;i<=m;i++)if(a[cs][i]>eps||a[cs][i]<-eps){nxt=i;break;}
            pivot(cs,nxt);
            m--;
        }
        for(int i=1;i<=m;i++){
            if(Base[i]>m+n){
                swap(Base[i],Base[m+1]);
                for(int j=0;j<=n;j++)a[j][i]=a[j][m+1];
                break;
            }
        }
        for(int i=1;i<=m;i++)a[0][i]=0;a[0][0]=tmp[0];
        for(int i=1;i<=m;i++)if(Base[i]<=m)a[0][i]=tmp[Base[i]];
        for(int i=1;i<=n;i++){
            if(Rest[i]<=m){
                for(int j=0;j<=m;j++)a[0][j]+=tmp[Rest[i]]*a[i][j];
            }
        }
        return 1;
    }
    void getval(){
        for(int i=1;i<=m;i++)val[i]=0;
        for(int i=1;i<=n;i++)if(Rest[i]<=m)val[Rest[i]]=a[i][0];
        //for(int i=1;i<=m;i++)printf("%.2f ",val[i]);puts("");
    }
    int solve(){
        if(!init())return 0;
        if(!opt())return -1;
        getval();
        return 1;
    }
}solver;
const double Simplex:: Inf=1e80;
const double Simplex:: eps=1e-8;
int main(){
    int m,n,type;
    scanf("%d%d%d",&m,&n,&type);
    solver.a[0][0]=0;
    for(int i=1;i<=m;i++)scanf("%lf",&solver.a[0][i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+1;j++){
            if(j==m+1)scanf("%lf",&solver.a[i][0]);
            else {
                scanf("%lf",&solver.a[i][j]);
                solver.a[i][j]=-solver.a[i][j];
            }
        }
    }
    solver.m=m,solver.n=n;
    int rep=solver.solve();
    if(rep==0)puts("Infeasible");
    else if(rep==-1)puts("Unbounded");
    else {
        printf("%.12f\n",solver.ans);
        if(type==1){
            for(int i=1;i<=m;i++)printf("%.12f%c",solver.val[i],i==m?'\n':' ');
        }
    }
}

再补充一个线性规划问题的描述：

本题中你需要求解一个标准型线性规划：

有 nn 个实数变量 x1,x2,…,xnx1,x2,…,xn 和 mm 条约束，其中第 ii 条约束形如 ∑nj=1aijxj≤bi∑j=1naijxj≤bi。

此外这 nn 个变量需要满足非负性限制，即 xj≥0xj≥0。

在满足上述所有条件的情况下，你需要指定每个变量 xjxj 的取值，使得目标函数 F=∑nj=1cjxjF=∑j=1ncjxj 的值最大。