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

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

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

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

#include<stdio.h>
#include<math.h>
#define N 1005
const double eps=1e-8;
double a[10005][1005], b[10005],c[1005],ans;
int m,n;
void pivot(int l,int e)
{
    b[l]/=a[l][e];
    for(int i=1; i<=n; i++)
        if (i!=e) a[l][i]/=a[l][e];
    a[l][e]=1.0/a[l][e];
    for(int i=1; i<=m; i++)
        if(i!=l&&fabs(a[i][e])>eps)
        {
            b[i]-=b[l]*a[i][e];
            for(int j=1; 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=1; i<=n; i++)
        if(i!=e)c[i]-=c[e]*a[l][i];
    c[e]=-c[e]*a[l][e];
}
void simplex()
{
    while(1)
    {
        int f,l;
        for(f=1; f<=n; f++)
            if (c[f]>eps) break;
        if(f>n) break;
        double Min=1e18,t;
        for(int i=1; i<=m; i++)
            if(a[i][f]>eps&&(t=b[i]/a[i][f])<Min)Min=t,l=i;
        if(l==-1) break;   
        pivot(l,f);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) scanf("%lf",&c[i]);
    for (int i=1,k; i<=m; i++)
    {
        scanf("%d",&k);
        for(int j=1; j<=k; j++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            for (int o=l; o<=r; o++) a[i][o]=1;
        }
        scanf("%lf",&b[i]);
    }
    simplex();
    printf("%d
",(int)(ans+0.5));
    return 0;
}