突然想看单纯形 BZOJ3265 志愿者招募加强版

本来的版本是可以差分之后建图利用网络流，这个题是板子题，就当存个板子，嘻嘻嘻

讲解可以到卿学姐的算法讲堂 https://www.bilibili.com/video/av7847726?from=search&seid=12330858507741778348

我的理解就是把它放进一个矩阵里去解决要满足的不等式问题，考虑他旁边的两个凸集顶点

#include<stdio.h>

#include<math.h>

#define N 1005

const double eps=1e-;

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

int m,n;

void pivot(int l,int e)

{

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

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

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

    a[l][e]=1.0/a[l][e];

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

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

        {

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

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

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

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

        }

    ans+=b[l]*c[e];

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

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

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

}

void simplex()

{

    while()

    {

        int f,l;

        for(f=; f<=n; f++)

            if (c[f]>eps) break;

        if(f>n) break;

        double Min=1e18,t;

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

            if(a[i][f]>eps&&(t=b[i]/a[i][f])<Min)Min=t,l=i;

        if(l==-) break;

        pivot(l,f);

    }

}

int main()

{

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

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

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

    {

        scanf("%d",&k);

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

        {

            int l,r;

            scanf("%d%d",&l,&r);

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

        }

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

    }

    simplex();

    printf("%d\n",(int)(ans+0.5));

    return ;

}