[POJ 1275] Cashier Employment【差分约束系统+二分答案】

• 2018-01-06
• 0
• 3

Problem:

Description

Input

Output

Sample Input

1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

Sample Output

1

Source

Solution:

本题是一道较难的差分约束题，不易找出所有的约束条件。

与题目中不同，为了防止下标越界，我们将下标整体增加 1。

令 R[i] 为时间 i (1 ≤ i ≤ 24) 需要的人数，A[i] 为时间 i (1 ≤ i ≤ 24) 开始工作的申请人数，S[i] 为所求的人数前缀和，则

由于工作时间为 8 小时，一个时间点需要的人数限定了其之前 8 个小时范围内的总人数，即

• S[i] - S[i - 8] ≥ R[i] (8 ≤ i ≤ 24) …… i)
• S[i] - S[i + 16] ≥ R[i] - S[24] (1 ≤ i ≤ 8) …… ii)

而申请人数的限定使得每个时间点所能录用的人数有所限制，即

• 0 ≤ S[i] - S[i - 1] ≤ A[i] (1 ≤ i ≤ 24)，可化为
• S[i] - S[i - 1] ≥ 0 (1 ≤ i ≤ 24) …… iii)
• S[i - 1] - S[i] ≥ -A[i] (1 ≤ i ≤ 24) ……iv)

至此差分约束条件列举完毕。但我们发现 ii) 右边存在未知数 S[24]，而 S[24] 的最小值正是我们要求的答案 ans。

所以我们可以二分枚举 ans，则 ans 必须满足 ii) 的变形

• S[i] - S[i + 16] ≥ R[i] - ans (1 ≤ i ≤ 8) …… v)

而此时我们又要保证 ans 是 S[24] 的最小值，所以

• S[24] ≥ ans …… vi)

联立 i) iii) iv) v) vi) 建图跑最长路，判断是否有负环 正环_{感谢ZqlwMatt大佬提醒}（负环 正环说明当前二分的 ans 无解），最小的有解 ans 即为答案。

由于涉及到有些边的边权会改变，需要删边操作，注意第一次没有加边时千万不能删边！

还有一定要注意不能犯低级错误，比如入队之后没有设置入队标记等。。

Code: O(kElogN), E为总边数(=73) [136K, 0MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;

int T, N;
int R[30], A[30];
// R[] is the number of required cashiers at each hour
// A[] is the number of applicants at each hour

struct Edge{
	int np, val;
	Edge *nxt;
};

struct Graph{
	Edge *V[30], E[150];
	int static_tope, tope;
	
	inline void clear() {tope = 0, memset(V, 0, sizeof(V));}
	
	inline void addedge(int u, int v, int w){
		E[++tope].np = v, E[tope].val = w;
		E[tope].nxt = V[u], V[u] = &E[tope];
	}
} G;

struct qnode{
	int id, step;
	
	qnode() {}
	qnode(int id, int step): id(id), step(step) {}
};

struct queue{
	#define inc(x) (x) = ((x) == 29 ? 1 : (x) + 1)
	qnode node[30];
	int fr, re;
	
	inline void clear() {fr = re = 0;}
	
	inline bool empty() {return fr == re;}
	
	inline void push(const qnode &x) {node[re] = x, inc(re);}
	
	inline void pop() {inc(fr);}
	
	inline qnode front() {return node[fr];}
} q;

int dis[30];
bool inq[30];

inline bool SPFA(int key){
	memset(dis, 0xc0, sizeof(dis));
	memset(inq, 0, sizeof(inq)), q.clear();
	q.push(qnode(0, 1)), inq[0] = 1, dis[0] = 0;
	while(!q.empty()){
		qnode u = q.front();
		q.pop(), inq[u.id] = 0;
		for(register Edge *ne = G.V[u.id]; ne; ne = ne->nxt)
			if(dis[u.id] + ne->val > dis[ne->np]){
				dis[ne->np] = dis[u.id] + ne->val;
				if(u.step == 25) return 0;
				if(!inq[ne->np]) q.push(qnode(ne->np, u.step + 1)), inq[ne->np] = 1;
				// Beware of those debased mistakes such as forgetting to set in-queue flags
			}
	}
	return 1;
}

inline void backupStatic() {G.static_tope = G.tope;}

inline void delExtra(){
	if(G.tope == G.static_tope) return;  // Do not delete at the first time when the extra edges are not even added
	G.tope = G.static_tope;
	G.V[0] = G.V[0]->nxt;
	for(register int i = 1; i <= 8; i++) G.V[i + 16] = G.V[i + 16]->nxt;
}

inline bool check(int key){
	delExtra();
	G.addedge(0, 24, key);
	// key == S[24] ==> S[24] >= key && key >= S[24]
	for(register int i = 1; i <= 8; i++) G.addedge(i + 16, i, R[i] - key);
	// S[i] + S[24] - S[i + 16] >= R[i] ==> S[i] >= S[i + 16] + R[i] - S[24] >= S[i + 16] + R[i] - key
	return SPFA(key);
}

int main(){
	scanf("%d", &T);
	while(T--){
		for(register int i = 1; i <= 24; i++) scanf("%d", R + i);
		scanf("%d", &N);
		memset(A, 0, sizeof(A));
		for(register int i = 1; i <= N; i++){
			int ti;
			scanf("%d", &ti);
			A[ti + 1]++;  // Beware of the subsription shift
		}
		G.clear();
		for(register int i = 1; i <= 24; i++) G.addedge(i - 1, i, 0), G.addedge(i, i - 1, -A[i]);
		// 0 <= S[i] - S[i - 1] <= A[i] ==> S[i] >= S[i - 1] && S[i - 1] >= S[i] - A[i]
		for(register int i = 8; i <= 24; i++) G.addedge(i - 8, i, R[i]);
		// S[i] - S[i - 8] >= R[i] ==> S[i] >= S[i - 8] + R[i]
		backupStatic();  // Backup the static part of the edges
		int lft = 0, rt = N + 1;
		while(lft < rt){  // Run binary search to find the minimum number of total cashiers
			int mid = lft + rt >> 1;
			if(check(mid)) rt = mid;
			else lft = mid + 1;
		}
		if(lft > N) puts("No Solution");
		else printf("%d\n", lft);
	}
	return 0;
}