poj1275 差分约束难再建模
题意;

Tehran的一家每天24小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决他的问题——超市在每天的不同时段需要不同数目的出纳员（例如：午夜时只需一小批，而下午则需要很多）来为顾客提供优质服务。他希望雇佣最少数目的出纳员。

经理已经提供你一天的每一小时需要出纳员的最少数量——R(0), R(1), ..., R(23)。R（0）表示从午夜到上午1：00需要出纳员的最少数目，R（1）表示上午1：00到2：00之间需要的，等等。每一天，这些数据都是相同的。有N人申请这项工作，每个申请者I在每24小时中，从一个特定的时刻开始连续工作恰好8小时，定义tI （0 <= tI <= 23）为上面提到的开始时刻。也就是说，如果第I个申请者被录取，他（她）将从tI 时刻开始连续工作8小时。

你将编写一个程序，输入R（I）（I = 0..23）和tI （I = 1..N），它们都是非负整数，计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的R（I）更多的出纳员在工作。

输入
输入文件的第一行为测试点个数（<= 20）。每组测试数据的第一行为24个整数表示R（0），R（1），...， R（23）（R（I）<= 1000）。接下来一行是N，表示申请者数目（0 <= N <= 1000），接下来每行包含一个整数tI （0 <= tI <= 23）。两组测试数据之间没有空行。

输出
对于每个测试点，输出只有一行，包含一个整数，表示需要出纳员的最少数目。如果无解，你应当输出“No Solution”。

样例输入

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

设num[i] 为来应聘的在第i个小时开始工作的人数

r[i] 为第i个小时至少需要的人数

x[i] 为招到的在第i个小时开始工作的人数

根据题意有：

0 <= x[i] <= num[i]

x[i] + x[i-1] + …+ x[i-7] >= r[i] (题目中的连续工作8小时)

再设 s[i] = x[1] + … + x[i]

则有： s[i] s[i-1] >= 0

s[i-1] s[i] >= num[i]

s[i] s[i-8] >= r[i], 8 <= i <= 24

s[i] s[i+16] >= r[i] s[24], 1<= i <= 7

还需要添加一个隐藏不等式： s[24] s[0] >= ans（枚举的答案）

通过枚举s[24],来检测是否满足条件，题目是求最小值，即求最长路，以0为源点。

#include <stdio.h>#define maxN 25//最大顶点数，这里是s[i]#define inf 0x7fffffffstruct Edge {int v, w, next;}edge[maxN * 30];//边int edgeNum;//边总数int dis[maxN];//最长路径中的dis[i]代表远点到i的最长距离int r[maxN];//r[i]标示i时刻至少需要多少人int num[maxN];//num[i]标示i时刻开始工作的人bool vis[maxN];//标示i是否进入队列int preEdge[maxN];//同一个起点的上一条边int cnt[maxN];//入队列的次数int queue[maxN * 30];//模拟队列int n;//输入的nvoid addEdge(int u, int v, int w)//添加新边{edge[edgeNum].v = v;edge[edgeNum].w = w;edge[edgeNum].next = preEdge[u];//以u为起点的上一条边preEdge[u] = edgeNum ++;}int spfa(int ans)//spfa算法实现{int head = 0, tail = 1;for (int i = 0; i <= 24; ++ i){dis[i] = -inf;vis[i] = false;cnt[i] = 0;}queue[0] = 0;dis[0] = 0;while (head < tail){int u = queue[head];int p = preEdge[u];vis[u] = true;while (p != -1){int v = edge[p].v, w = edge[p].w;if (dis[v] < dis[u] + w){dis[v] = dis[u] + w;if (!vis[v]){vis[v] = true;queue[tail] = v;tail ++;}if(++cnt[v] > 24){return 0;}}p = edge[p].next;}head ++;vis[u] = false;}if (dis[24] == ans){return 1;}return 0;}void buildGraph(int ans)//建图这也是本题目的关键，建模。。。。{edgeNum = 0;for (int i = 0; i <= 24; ++ i){preEdge[i] = -1;}addEdge(0,24,ans);  for(int i = 1;i <= 24;++i)  {   addEdge(i - 1,i,0);  addEdge(i,i - 1,-num[i]);  }  for(int i = 1;i <= 8;++i)    addEdge(i + 16,i,r[i] - ans);  for(int i = 9;i <= 24;++i)   addEdge(i - 8,i,r[i]);  }int main()//主函数{intcases;scanf("%d", &cases);while (cases --){bool flag = false;;for (int i = 1; i <= 24; ++ i){scanf("%d", &r[i]);num[i] = 0;}scanf("%d", &n);int t;for (int i = 0; i < n; ++ i){scanf("%d", &t);num[t + 1] ++; }for (int i = 0; i <= n; ++ i){buildGraph(i);if (spfa(i) == 1){flag = true;printf("%d\n", i);break;}}if (!flag){printf("No Solution\n");  }}return 0;}