POJ1275 Cashier Employment 二分、差分约束

时间:2022-06-30 07:41:30

传送门

题意太长


为了叙述方便,将题意中的$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 ;
}