＜算法競賽進階指南＞ 差分限制 雇傭收銀員

一家超市要每天 24 小時營業，為了滿足營業需求，需要雇傭一大批收銀員。

已知不同時間段需要的收銀員數量不同，為了能夠雇傭盡可能少的人員，進而減少成本，這家超市的經理請你來幫忙出謀劃策。

經理為你提供了一個各個時間段收銀員最小需求數量的清單 R(0),R(1),R(2),…,R(23)。

R(0) 表示午夜 00:00 到淩晨 01:00 的最小需求數量，R(1) 表示淩晨 01:00 到淩晨 02:00 的最小需求數量，以此類推。

一共有 NN 個合格的申請人申請崗位，第 i 個申請人可以從 ti 時刻開始連續工作 8 小時。

收銀員之間不存在替換，一定會完整地工作 8 小時，收銀台的數量一定足夠。

現在給定你收銀員的需求清單，請你計算最少需要雇傭多少名收銀員。

輸入格式

第一行包含一個不超過 20 的整數，表示測試資料的組數。

對于每組測試資料，第一行包含 24 個整數，分别表示 R(0),R(1),R(2),…,R(23)。

第二行包含整數 N。

接下來 NN 行，每行包含一個整數 ti。

輸出格式

每組資料輸出一個結果，每個結果占一行。

如果沒有滿足需求的安排，輸出 

No Solution

。

資料範圍

0≤R(0)≤1000,

0≤N≤1000,

0≤ti≤23

輸入樣例：

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
           

輸出樣例：

1
           

若不清楚差分限制算法的同學可以看看這篇部落格：(16條消息) 《圖論：差分限制算法詳解 + 算法證明》+ 模闆題：糖果_wsh1931的部落格-CSDN部落格

假設x[i]表示第i個時間段雇用了多少人，nums[i]從 i 這個點來的人數。

1:  0 <= x[i] <= nums[i];（即第i個時間段所選擇的人數必需小于等于i 這個時間段來的人數）

2: x[i - 7] + x[i - 6] + .....x[i] >=  R[i];（即第 i 個時間段之前的8個小時雇傭的人數必需大于題目要求的在第 i 個時間段的人數)。

我們可以看出條件二并不符合差分限制算法的形式，是以我們可以求一個x[i]的字首和s[i], s[i]表示前 i 個時間段雇傭了多少人

因為涉及字首和需要把s[0]空出，是以我們可以把所有的時間從[0, 23]映射成[1, 24];

是以條件一可以轉換成：

0 <= s[i] - s[i - 1] <= nums[i];

條件二可以轉換成;

(i >= 8)：s[i] - s[i - 8] >= R[i];

(0 < i < 7)：s[i] + s[24] - s[i + 16] >= R[i];

這裡可以這樣了解将1 2 3 4 ..... 24看成 1 2 3 4 .... 24 1 2 3 4 ... 24即若雇傭員到了24點，但還未滿8小時再從1開始工作知道滿8小時為止

這裡求得是最少的雇傭員，則求的是最長路。

将2個條件總結一下即：

1:  s[i] >= s[i - 1];

2:  s[i - 1] >= s[i] - nums[i];

3:  (i >= 8) s[i] >= s[i - 8] + R[i];

4:  (0 < i < 7) s[i] >= R[i] + s[i + 16] - s[24]

第四條結論仍然不符合差分限制因為0≤N≤1000是以我們可以從0 到 1000枚舉s[24]這樣s[24]就成了常數，這裡要注意要将s[24]變成常數還要加兩條邊分别是: s[24] >= c, s[24] <= c，s[24]最終才為c,  c為s[24]枚舉的常數值

是以 5 ：s[24] >= c, s[24] <= c ->  s[24] >= s[0] + c, s[0] >= s[24] - c即從0 -> 24 連一條權值為c的邊，再從24 -> 0連一條權值為c的邊

因為條件一：s[i] >= s[i - 1]是以從0出發可以周遊所有的點，即可以周遊所有的邊是以不需要建立超級源點

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 30, M = N * 3;//24個點，條件一，二的邊數分别為N, 條件三，四總共的邊數為N

int n;
int R[N];
int cnt[N];
bool st[N];
int nums[N];
int dist[N];
int h[N], e[M], ne[M], w[M], idx;

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

void build(int s24)
{
    idx = 0;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= 24; i ++ ) add(i - 1, i, 0);//條件一
    for (int i = 1; i <= 24; i ++ ) add(i, i - 1, -nums[i]);//條件二
    for (int i = 8; i <= 24; i ++ ) add(i - 8, i, R[i]);//條件三
    for (int i = 0; i < 7; i ++ ) add(i + 16, i, R[i] - s24);//條件四
    add(0, 24, s24), add(24, 0, -s24);//條件5
}

bool spfa()
{
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, -0x3f, sizeof dist);
    
    queue<int> q;
    q.push(0);
    st[0] = true;
    dist[0] = 0;
    
    while (q.size())
    {
        int t = q.front();
        q.pop();
        
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            
            if (dist[j] < dist[t] + w[i])
            {
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= 25) return false;//包括0點
                
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return true;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 1; i <= 24; i ++ ) scanf("%d", &R[i]);
        
        cin >> n;
        memset(nums, 0, sizeof nums);
        for (int i = 0; i < n; i ++ )
        {
            int t;
            scanf("%d", &t);
            nums[++ t] ++ ;//從【0，23】映射成【1，24】
        }
        
        bool is_true = false;
        for (int i = 0; i <= 1000; i ++ ) //枚舉s[24]的人數即前24的時間段内雇傭的總人數
        {
            build(i);
            if (spfa())
            {
                printf("%d\n", i);
                is_true = true;
                break;
            }
        }
        
        if (!is_true) puts("No Solution");//若沒找到。
    }
    
    return 0;
}