题意： 这个解题报告描述的相当详细了。就不多说了;
差分约束关键是找出约束条件，然后建图。最后就是套spfa或者bellman_ford的模板就是了;
#include#include #include #include #define maxn 25using namespace std;struct node{ int v,w; int next;}g[10*maxn];int cnt,pre[maxn],ind[maxn],dis[maxn];bool inq[maxn];int R[maxn],num[26];const int inf = 9999999;void init(){ cnt = 0; memset(pre,-1,sizeof(pre)); memset(ind,0,sizeof(ind)); memset(inq,false,sizeof(inq));}void add(int u,int v,int w){ g[cnt].v = v; g[cnt].w = w; g[cnt].next = pre[u]; pre[u] = cnt++;}bool spfa(int s){ int i; queue q; for (i = 0; i < maxn; ++i) dis[i] = -inf; dis[s] = 0; q.push(s); inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); if (++ind[u] > 24) return false; inq[u] = false; for (i = pre[u]; i != -1; i = g[i].next) { int v = g[i].v, w = g[i].w; if (dis[v] < dis[u] + w) { dis[v] = dis[u] + w; if (!inq[v]) { inq[v] = true; q.push(v); } } } } return true;}int main(){ int i,t,pos,n; scanf("%d",&t); while (t--) { memset(num,0,sizeof(num)); for (i = 1; i <= 24; ++i) scanf("%d",&R[i]); scanf("%d",&n); for (i = 0; i < n; ++i) { scanf("%d",&pos); num[pos + 1]++; } int l = 0, r = n; bool flag = false; while (l < r) { init(); int mid = (l + r)>>1; for (i = 1; i <= 24; ++i) { add(i - 1,i,0); add(i,i - 1,-num[i]); } for (i = 8; i <= 24; ++i) add(i - 8,i,R[i]); for (i = 1; i <= 7; ++i) add(i + 16,i,R[i] - mid); add(0,24,mid); if (spfa(0)) { r = mid; flag = true; } else { l = mid + 1; } } if (flag) printf("%d\n",r); else printf("No Solution\n"); } return 0;}