BZOJ 3112 [Zjoi2013]防守战线 线性规划

题意:

方法:线性规划

解析:

与上一题相似。相同使用对偶原理解题。解法不再赘述。

代码:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 1010

#define M 10010

#define INF 0x7f7f7f7f

using namespace std;

double a[N][M];

int n,m;

int check()

{

    for(int i=1;i<=m;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<=n;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<=m;i++)

        {

            if(i==t)a[choseline][i]/=di;

            a[choseline][i]/=di;

        }

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

        {

            if(i==choseline||!a[i][t])continue;

            if(i==0)a[i][0]+=a[i][t]*a[choseline][0];

            else a[i][0]-=a[i][t]*a[choseline][0];

            double l=a[i][t];

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

            {

                if(j==t)a[i][j]=-l*a[choseline][j];

                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[i][0]);

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

    {

        int l,r,d;

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

        for(int j=l;j<=r;j++)

            a[j][i]=1;

    }

    Simplex();

    printf("%.0lf\n",a[0][0]);

}