题意：一个商店，告诉你一天每个小时里至少需要的人数，以及来应聘的人数的工作的起始时间，固定工作8小时，求最少应该雇佣的人数。
思路：设 s[i] 表示在前 i 小时，总开始工作的人数，所以， i>=8时， 有 s[i] - s[i-8] >= i时刻需要的人数，
i<8 时， 有 s[i]+s[24]-s[i+16]>=i时刻需要的人数 。 同时，对于相邻时间会有 0<=s[i] - s[i-1]<=i时刻开始工作的人数。在这里会发现 s[24] 就是我们要求的答案，但就这样的话还是求不出，所以枚举s[24];
想法：难点在建立不等式，即建图。（大佬厉害）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
const int maxn = 50;
const int inf = 0x3f3f3f3f;
using namespace std;
struct note{
int to, w;
note(int to1, int w1){
to = to1, w = w1;
}
};
vector <note> maps[maxn];
int need[maxn], work[maxn], ans;
//need[i] i时刻需要的人数
//work[i] i时刻开始工作的人数
void init(){//要枚举答案， 所以每次要初始化，并建图
for(int i=0; i<=24; i++)
maps[i].clear();
for(int i=1; i<=24; i++){
maps[i-1].push_back(note(i, 0)); // s[i] - s[i-1] >= 0
maps[i].push_back(note(i-1, -work[i]));
//s[i] - s[i-1] <= work[i] ---> s[i-1] - s[i] >= -work[i]
if(i>=8)
maps[i-8].push_back(note(i, need[i])); //s[i] - s[i-8] >= need[i]
else
maps[16+i].push_back(note(i, need[i]-ans)); //s[i] - s[i+16] >= need[i]-ans
}
maps[0].push_back(note(24, ans)); //s[24]-s[0]>=ans （容易忘记）
}
bool spfa(){
int dis[maxn], cnt[maxn];
//图有可能回出现负环， cnt[i] 记录 i 点入队列的次数
bool vis[maxn];
for(int i=0; i<=24; i++)
dis[i] = -inf, vis[i] = false, cnt[i] = 1;
dis[0] = 0, vis[0] = true, cnt[0] = 1;
queue <int> q;
q.push(0);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i=0, len = maps[u].size(); i<len; i++){
int v = maps[u][i].to, w = maps[u][i].w;
if(dis[v] < dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
cnt[v]++;
if(cnt[v] > 24)
return false; //存在负环，无解
vis[v] = true;
q.push(v);
}
}
}
}
if(dis[24] == ans)
return true;
return false;
}
int main()
{
int t;
scanf("%d", &t);
while(t--){
for(int i=1; i<=24; i++){
scanf("%d", &need[i]);
}
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++){
int j;
scanf("%d", &j);
work[j+1]++;
}
for(ans=0; ans<=n; ans++){ //枚举
init();
if(spfa()){
break;
}
}
if(ans > n)
printf("No Solution
");
else
printf("%d
", ans);
}
return 0;
}