BZOJ 1061 [Noi2008]志愿者征募 线性规划

题意:链接

方法:线性规划

解析:

不妨对样例加以阐释

3 3

2 3 4

1 2 2

2 3 5

3 3 2

不妨设$X_i$代表第i种志愿者选$X_i$个人

那么显然，这题的限制为

$X_1>=2$

$X_1+X_2>=3$

$X_2+X_3>=4$

而我们要做的是使$2*X_1+5*X_2+2*X_3$最小化

且$X_i>=0$

但这显然没有基本可行解，那么就不能用单纯形搞了吗？

并不是

有一个强大的东西叫对偶原理

什么是对偶原理呢？

对于本人的代码

设矩阵$a[i][j]$

其中$a[0][i]$代表目标函数的系数

$a[i][0]$代表第i个限制的常数项

$a[i][j]$代表第i个限制的第j个非基本变量的系数

那么对偶原理相当于什么呢？

将这个a转置，并且转置后形成的矩阵又能满足一个线性规划。

而这个线性规划是一个标准型线性规划

我们只需要求一下转置后矩阵对应的标准型线性规划的目标函数的最大值即可，此时这个值同时代表原线性规划的最小值。

至于证明？

好像算导有吧。

我并不会。

总之这道题就可以解了。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
#define M 10010
#define INF 0x7f7f7f7f
using namespace std;
int n,m;
double a[M][N];
int check()
{
    for(int i=1;i<=n;i++)
        if(a[0][i]>0)return i;
    return 0;
}
void Simplex()
{
    while(int t=check())
    {
        double limit=INF;
        int choseline;
        for(int i=1;i<=m;i++)
        {
            if(a[i][t]<=0)continue;
            if(a[i][0]/a[i][t]<limit)limit=a[i][0]/a[i][t],choseline=i;
        }
        if(limit==INF){a[0][0]=INF;break;}
        double di=a[choseline][t];
        for(int i=0;i<=n;i++)
        {
            if(i==t)a[choseline][i]/=di;
            a[choseline][i]/=di;
        }
        for(int i=0;i<=m;i++)
        {
            if(i==choseline||!a[i][t])continue;
            if(i==0)a[i][0]+=a[choseline][0]*a[i][t];
            else a[i][0]-=a[i][t]*a[choseline][0];
            double l=a[i][t];
            for(int j=1;j<=n;j++)
            {
                if(j==t)a[i][j]=-l*a[choseline][t];
                else a[i][j]-=l*a[choseline][j];
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lf",&a[0][i]);
    for(int i=1;i<=m;i++)
    {
        int s,t;
        scanf("%d%d",&s,&t);
        for(int j=s;j<=t;j++)a[i][j]=1;
        scanf("%lf",&a[i][0]);
    }
    Simplex();
    printf("%.0lf\n",a[0][0]);
}