bzoj3550: [ONTAK2010]Vacation&&bzoj3112: [Zjoi2013]防守战线

学了下单纯形法解线性规划

看起来好像并不是特别难，第二个code有注释。我还有...*=-....这个不是特别懂

第一个是正常的，第二个是解对偶问题的

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const double eps=1e-;

int n,m; double sum;

double a[][],b[],c[];

void pivot(int o,int e)

{

    b[o]/=a[o][e];

    for(int i=;i<=n;i++)

        if(i!=e)a[o][i]/=a[o][e];

    a[o][e]=/a[o][e];

    for(int i=;i<=m;i++)

        if(i!=o&&fabs(a[i][e])>eps)

        {

            b[i]-=b[o]*a[i][e];

            for(int j=;j<=n;j++)

                if(j!=e)a[i][j]-=a[o][j]*a[i][e];

            a[i][e]*=-a[o][e];

        }

    sum+=c[e]*b[o];

    for(int i=;i<=n;i++)

        if(i!=e)c[i]-=a[o][i]*c[e];

    c[e]*=-a[o][e];

}

void simplex()

{

    int e,o; double d;

    while()

    {

        d=;

        for(int i=;i<=n;i++)

            if(c[i]>d)d=c[i],e=i;

        if(d==)return ;

        d=(<<);

        for(int i=;i<=m;i++)

            if(a[i][e]>eps&&d>b[i]/a[i][e])

                d=b[i]/a[i][e],o=i;

        if(d==(<<)){sum=(<<);return ;}

        pivot(o,e);

    }

}

int main()

{

    int K;

    scanf("%d%d",&n,&K);m=*n+;n*=;

    for(int i=;i<=n;i++)scanf("%lf",&c[i]);

    for(int i=;i<=m;i++)

    {

        b[i]=K;

        for(int j=;j<=n/;j++)a[i][i+j-]++;

    }

    for(int i=;i<=n;i++)

        b[m+i]=,a[m+i][i]++;

    m+=n;

    sum=;simplex();

    printf("%.0lf\n",sum);

    return ;

}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const double eps=1e-;

int n,m; double sum;

double a[][],b[],c[];

//解的过程中，由于基变量xi=ci，所以c也代表放在当前约束的基变量取值

void pivot(int o,int e)//把作为第o个约束的基变量用e替换

{

    c[o]/=a[o][e];//没有替换之前，e的取值被当前限制，是c[o]/a[i][e]，先令x=c

    for(int i=;i<=m;i++)//把e的系数消掉，其实常数项c也是同理的

        if(i!=e)a[o][i]/=a[o][e];

    a[o][e]=/a[o][e];//难点！取倒数相当于保留了自己的常数项，而除以了上一个的常数项，这样下面就可以直接消除上一个的影响了

    for(int i=;i<=n;i++)

        if(i!=o&&fabs(a[i][e])>eps)//对于其它的约束条件，把离基的变量用进基的变量替代

        {

            c[i]-=c[o]*a[i][e];

            for(int j=;j<=m;j++)

                if(j!=e)a[i][j]-=a[o][j]*a[i][e];

            a[i][e]*=-a[o][e];

        }

    sum+=b[e]*c[o];//系数乘以值

    for(int i=;i<=m;i++)//对于第i个变量当前已经用了b[e]*a[o][i]来贡献答案了

        if(i!=e)b[i]-=a[o][i]*b[e];

    b[e]*=-a[o][e];

}

void simplex()

{

    int e,o; double d;

    while()

    {

        d=;//找进基的变量

        for(int i=;i<=m;i++)//基变量的b一定<=0，在非基变量中找一个对答案贡献最大(系数最大)的进基

            if(b[i]>d)d=b[i],e=i;

        if(d==)return ;

        d=(<<);//找离基的变量，进基变量系数的非负比要最小

        for(int i=;i<=n;i++)//找对e的最小约束（即用此新角点截距最小，也就是当前e的取值被这个约束条件约束）离基

            if(a[i][e]>eps&&d>c[i]/a[i][e])

                d=c[i]/a[i][e],o=i;

        if(d==(<<)){sum=(<<);return ;}

        pivot(o,e);

    }

}

int main()

{

    int l,r;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%lf",&c[i]);

    memset(a,,sizeof(a));

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%lf",&l,&r,&b[i]);

        for(int j=l;j<=r;j++)a[j][i]++;

    }

    simplex();

    printf("%.0lf\n",sum);

    return ;

}

---恢复内容结束---