POJ1275 Cashier Employment 二分、差分约束

传送门

题意太长

为了叙述方便，将题意中的$0$点看作$1$点，$23$点看做$24$点

考虑二分答案（其实从小到大枚举也是可以的）

设$x_i$是我们选的雇员第$i$小时开始工作的人数，$s_i$是$x_i$的前缀和，又设$p_i$为可以在第$i$小时开始工作的人数，$q_i$表示第$i$小时需要的人数，$mid$为我们二分的答案

那么我们有

$$s_i-s_{i-8} \geq q_i , 8 \leq i \leq 24$$

$$s_i - s_{i+16} \geq q_i - mid , 1 \leq i \leq 7$$

$$s_{i - 1} - s_i \geq -p_i$$

$$s_i - s_{i-1} \geq 0$$（很容易漏掉）

$$s_{24}-s_{0} \geq mid$$

最后一条边的原因是：注意到第二种边中我们强制了$s_{24} = mid$，但是实际跑出来的解有可能$s_{24} \neq mid$，那么第二个式子就很有可能不成立。但是当$mid < s_{24}$时令$mid = s_{24}$时条件显然仍然成立，所以我们只需要让$s_{24} < mid$的时候强制让$s_{24} \geq mid$才行。

直接差分约束求最长路就完了

差分约束有很多细节需要注意，掉了很多次坑qwq（比如每一次的queue都要清空）

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 inline int read(){

     int a = ;

     bool f = ;

     char c = getchar();

     while(c != EOF && !isdigit(c)){

         if(c == '-')

             f = ;

         c = getchar();

     }

     while(c != EOF && isdigit(c)){

         a = (a << ) + (a << ) + (c ^ '');

         c = getchar();

     }

     return f ? -a : a;

 }

 struct Edge{

     int end , upEd , w;

 }Ed[*];

 int num[] , x[] , maxDis[] , flo[] , head[] , cntEd , preHead[] , preCnt;

 queue < int > q;

 bool inq[];

 inline void addEd(int a , int b , int c){

     Ed[++cntEd].end = b;

     Ed[cntEd].upEd = head[a];

     Ed[cntEd].w = c;

     head[a] = cntEd;

 }

 inline bool check(int mid){

 while(!q.empty())q.pop();

     memcpy(head , preHead , sizeof(preHead));

     cntEd = preCnt;

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

         addEd(i +  , i , num[i] - mid);

     addEd( ,  , mid);

     memset(maxDis , -0x3f , sizeof(maxDis));

     memset(inq ,  , sizeof(inq));

     memset(flo ,  , sizeof(flo));

     maxDis[] = ;

     q.push();

     while(!q.empty()){

         int t = q.front();

         q.pop();

         inq[t] = ;

         for(int i = head[t] ; i ; i = Ed[i].upEd)

             if(maxDis[Ed[i].end] < maxDis[t] + Ed[i].w){

                 maxDis[Ed[i].end] = maxDis[t] + Ed[i].w;

                 if((flo[Ed[i].end] = flo[t] + ) >= )

                     return false;

                 if(!inq[Ed[i].end]){

                     inq[Ed[i].end] = ;

                     q.push(Ed[i].end);

                 }

             }

     }

     return true;

 }

 int main(){

 #ifdef LG

     freopen("1275.in" , "r" , stdin);

 #endif

     for(int T = read() ; T ; T--){

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

             num[i] = read();

         cntEd = ;

         memset(head ,  , sizeof(head));

         memset(x ,  , sizeof(x));

         int P = read() , L =  , R = P + ;

         for(int i = P ; i ; i--)

             x[read() + ]++;

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

             addEd(i , i +  , );

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

             addEd(i -  , i , num[i]);

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

             addEd(i , i -  , -x[i]);

         memcpy(preHead , head , sizeof(head));

         preCnt = cntEd;

         while(L < R){

             int mid = L + R >> ;

             check(mid) ? R = mid : L = mid + ;

         }

         if(L > P)

             puts("No Solution");

         else

             cout << L << endl;

     }

     return ;

 }

巴特西

POJ1275 Cashier Employment 二分、差分约束

最新文章

热门文章