BZOJ 3265 志愿者招募加强版(单纯形)

3265: 志愿者招募加强版

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 848  Solved: 436
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

3 3
2 3 4
1 1 2 2
1 2 3 5
1 3 3 2

Sample Output

14

HINT

题解：这一题类似于BZOJ1061,(几乎相同，只是把一段连续区间改为几段连续区间而已)，做法一样，单纯形模板直接套就行；

具体看代码：

 

参考代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define cls(x, val) memset(x,val,sizeof(x))

 #define RI register int

 #define eps 1e-6

 typedef long long ll;

 typedef unsigned long long ull;

 const int INF=0x3f3f3f3f;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>'') {if(ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 const int N=;

 const int M=;

 int n,m;

 double a[M][N],b[M],c[M],v;

 inline void pivot(int l,int e)//矩阵的转秩

 {

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

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

     {

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

     }

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

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

     {

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

         {

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

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

             {

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

             }

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

         }

     }

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

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

     {

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

     }

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

 }

 inline double simplex()

 {

     while()

     {

         int e=,l=;

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

         {

             if(c[e]>eps) break;

         }

         if(e==n+) return v;

         double mn=INF;

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

         {

             if(a[i][e]>eps&&mn>b[i]/a[i][e]) mn=b[i]/a[i][e],l=i;

         }

         if(mn==INF) return INF;

         pivot(l,e);

     }

 }

 int main()

 {

     n=read(),m=read();

     for(RI i=;i<=n;++i) c[i]=read();

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

     {

         RI k=read();

         while(k--)

         {

             int s,t;

             s=read(),t=read();

             for(RI j=s;j<=t;++j) a[i][j]=1.0;

         }

         b[i]=read();

     }

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

     return ;

 }