HDU 1529 Cashier Employment （差分约束）

题意：德黑兰的某国营商店需要聘用一批员工，不同的时间有不同的人员需求，能够雇佣到的人数也不同。然而你一旦聘用了一个人，他就会跟着你干8个小时。输入24个时间点的需求与劳动力人数，输出满足需求最少需要的人数，不行就输出no solution。

题解：差分约束
设$d[i]$表示从0点到$i?1$点（包括$i?1$）雇佣的人数。答案就是$d[24]$。
每个点$i$的需求和供应人数分别用$r[i]$和$a[i]$表示。

可得约束方程：
$d[i+1]?d[i]>=0$，每个点雇佣人数非负
$d[i]?d[i+1]<=a[i]$，每个点雇佣人数不超过提供的人数

考虑区间上的约束，因为每个人会连续干8个小时，可得约束方程：
$d[i]?d[i?8]>=r[i?1]$，即八个小时之内的人都会在$i?1$点工作，那么人数要满足需求。

考虑跨天的情况：
$d[24]?d[i+16]+d[i]>=r[i?1]$

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int maxn = 1e3 + 5;
int t, r[24], n, a[maxn], x;
struct node {
    int v, nxt, w;
}edge[maxn << 2];
int vis[maxn], d[maxn], head[maxn], k, s, mark[maxn];
void add(int u, int v, int w) {
    edge[++k].nxt = head[u];edge[k].v = v;edge[k].w = w;head[u] = k;
}
bool spfa() {
    for (int i = 0; i <= 24; i++) {
    vis[i] = mark[i] = 0;d[i] = -0x3f3f3f3f;}queue<int> q;q.push(s);vis[s] = 1;d[s] = 0;mark[s] = 1;while (!q.empty()) {
    int u = q.front(); q.pop();vis[u] = 0;for (int i = head[u]; i; i = edge[i].nxt) {
    int v = edge[i].v, w = edge[i].w;if (d[v] < d[u] + w) {
    d[v] = d[u] + w;if (vis[v]) continue;vis[v] = 1;if (++mark[v] > 24) return false;q.push(v);}}}return true;
}
bool check(int mid) {
    k = 0;for (int i = 0; i <= 24; i++) head[i] = 0;for (int i = 0; i < 24; i++) {
    add(i, i + 1, 0);add(i + 1, i, -a[i]);}for (int i = 8; i <= 24; i++) {
    add(i - 8, i, r[i - 1]);}for (int i = 1; i <= 7; i++) {
    add(16 + i, i, r[i - 1] - mid);}add(0, 24, mid);add(24, 0, -mid);s = 0;return spfa();
}
int main() {
    scanf("%d", &t);while (t--) {
    memset(a, 0, sizeof(a));for (int i = 0; i < 24; i++) scanf("%d", &r[i]);scanf("%d", &n);for (int i = 1; i <= n; i++) {
    scanf("%d", &x);a[x]++;}int mid;   //d[24]int l = 0, r = n, ans = -1;while (l <= r) {
    mid = (l + r) >> 1;if (check(mid)) {
    ans = mid;r = mid - 1;}else l = mid + 1;}if (ans == -1) puts("No Solution");else printf("%d\n", ans);}return 0;
}