超市在每个时间都有需要的人数（24小时）比如 1 0 0 0 0 。。。。也就是说在第0个小时的时候要用一个人，其他的时间都不用人，在给你一些人工作的起始时间，如果雇佣了这个人，那么这个人就会从自己的其实时间工作8个小时后离开，给你需求和可雇佣的员工，问你满足需求超时最少雇佣多少人。
思路：
经典的差分约束，之前尝试过很多次都没AC，今天终于AC了，现在我们就来找各种隐含条件。
设：
num[i] 表示第i个小时开始的有多少个人。
r[i] 表示第i个小时最少雇佣多少人。
s[i] 表示1。。。i小时开始工作的有多少人。 (我们以S为核心建图)
限制条件：
第i个小时雇佣并开始工作的人数 >= 0
则 s[i] - s[i-1] >= 0
第i个小时雇佣并开始工作的人数 <= num[i]
则 s[i] - s[i-1] <= num[i] 转化成 s[i-1] - s[i] >= -num[i]
第i个小时雇佣的人数 >= r[i]
则 s[i] - s[i-8] >= r[i] (i >= 8 && i <= 24)
s[24] + s[i] - s[i + 16] >= r[i] (i <= 7)
观察最后一个不等式，出现了三个变量，不符合差分约束形式，所以我们就直接二分枚举
s[24]的值，也就是二分枚举雇佣人数的值，这样就把最后一个转换成
s[i] - s[i + 16] >= r[i] - mid
最后别忘了还有一个限制条件就是s[24] - s[0] = mid,=怎么建边呢？我们可以这样
s[24] - s[0] >= mid并且 s[24] - s[0] <= mid
第二个转换成 s[0] - s[24] >= -mid;
这样就可以二分下去了。。。
#include<stdio.h> #include<string.h> #include<queue> #define N_node 30 #define N_edge 10000 #define INF 1000000000 using namespace std; typedef struct { int to ,cost ,next; }STAR; STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node]; int r[30] ,num[1100]; void add(int a ,int b ,int c) { E[++tot].to = b; E[tot].cost = c; E[tot].next = list[a]; list[a] = tot; } bool Spfa(int s ,int n) { for(int i = 0 ;i <= n ;i ++) s_x[i] = -INF; int mark[N_node] = {0}; int in[N_node] = {0}; s_x[s] = 0; mark[s] = in[s] = 1; queue<int>q; q.push(s); while(!q.empty()) { int xin ,tou; tou = q.front(); q.pop(); mark[tou] = 0; for(int k = list[tou] ;k ;k = E[k].next) { xin = E[k].to; if(s_x[xin] < s_x[tou] + E[k].cost) { s_x[xin] = s_x[tou] + E[k].cost; if(!mark[xin]) { mark[xin] = 1; if(++in[xin] > n) return 0; q.push(xin); } } } } return 1; } bool ok(int mid) { memset(list ,0 ,sizeof(list)); tot = 1; for(int i = 1 ;i <= 24 ;i ++) { add(i - 1 ,i ,0); add(i ,i - 1 ,-num[i]); if(i >= 8) add(i - 8 ,i ,r[i]); else add(i + 16 ,i ,r[i] - mid); } add(0 ,24 ,mid); add(24 ,0 ,-mid); return Spfa(0 ,24); } int main () { int t ,i ,a ,n; scanf("%d" ,&t); while(t--) { for(i = 1 ;i <= 24 ;i ++) scanf("%d" ,&r[i]); scanf("%d" ,&n); memset(num ,0 ,sizeof(num)); for(i = 1 ;i <= n ;i ++) { scanf("%d" ,&a); num[a+1] ++; } int low ,mid ,up; low = 0 ,up = n; int ans = -1; while(low <= up) { mid = (low + up) >> 1; if(ok(mid)) { ans = mid; up = mid - 1; } else low = mid + 1; } if(ans == -1) puts("No Solution"); else printf("%d " ,ans); } return 0; }