bzoj1061题解

【解题思路】

　　设类型i的志愿者，即第S_i天~第T_i天工作的志愿者，共招募x_i个，于是有不等式组Σx_j≥A_i(Sj≤i≤Tj)。

　　这样，题目就变成了求一组满足一次不等式组的x_i，使ΣC_ix_i最小，即标准的线性规划形式。

　　本人比较懒。。并不想建图跑费用流之类的。。于是写了单纯形。。复杂度O(松)。

【参考程序】

 1 #pragma GCC optimize(2)
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #define REP(i,low,high) for(register int i=(low);i<=(high);i++)
 6 #define INF 1e10
 7 #define eps 1e-7
 8 using namespace std;
 9 inline bool getmin(double &tar,const double &pat) {return pat+eps<tar?tar=pat,1:0;}
10 double a[1010][10010]; int m,n;
11 inline int check() {REP(i,1,m) if(a[i][0]>eps) return i; return 0;}
12 inline double Simplex()
13 {
14     while(int x=check())
15     {
16         int y=0; double lim=INF; REP(i,1,n) if(a[x][i]>eps&&getmin(lim,a[0][i]/a[x][i])) y=i;
17         if(!y) return a[0][0]=INF; double p=1.0/a[x][y]; a[x][y]=1.0; REP(i,0,m) a[i][y]*=p;
18         REP(i,1,n) if(i!=y)
19         {
20             double now=a[x][i];
21             if(fabs(now)>eps) {a[0][i]-=now*a[0][y]; REP(j,1,m) a[j][i]-=now*a[j][y]; a[x][i]=-now*p;}
22         }
23         double now=a[x][0]; a[0][0]+=now*a[0][y]; REP(i,1,m) a[i][0]-=now*a[i][y]; a[x][0]=-now*p;
24     }
25     return a[0][0];
26 }
27 int main()
28 {
29     scanf("%d%d",&m,&n); REP(i,1,m) scanf("%lf",&a[i][0]);
30     REP(i,1,n) {int S,T; scanf("%d%d",&S,&T); REP(j,S,T) a[j][i]=1.0; scanf("%lf",&a[0][i]);}
31     return printf("%.0lf
",Simplex()+eps),0;
32 }

View Code