poj1275

题目大意:

每天有24小时，每个小时需要一定的人。有m个人每个人会有一个开始工作的时间，每个人会工作8小时，问至少需要多少人才能完成任务。如果这m个人也不能完成任务就输出"No Solution"。每天会不断的循环下去，也就是今天20点雇佣的人，会工作到明天4点。

思路

用s[i]表示前i个小时选的人数，ans表示选的人数，r[i]表示第i个小时需要的人数。h[i]表示第i个小时可以雇佣的人数。

约束条件：

(1): 每个小时雇佣的人数不可能为负数——

\(s[i]-s[i-1]\geqslant0\)

(2): 每个小时雇佣的人数不应该超过这个小时所需要的人数——

\(s[i]-s[i-1]\leqslant r[i]\)

(3): 前8个小时雇佣的人数不应该小于当前需要的人数——

\(s[i]-s[i-8]\geqslant r[i] (i>8）\)

\(ans+s[i]-s[i+16]\leqslant r[i] (r<=8)\)

(4): 每天的人数应该为ans——

\(s[24]-s[0]\geqslant ans\)

\(s[24]-s[0]\leqslant ans\)

代码:

/*s[i]表示前i个小时选的人数，r[i]表示第i个小时需要的人数，h[i]表示第i个小时报名的人数
s[i]-s[i-1]>=0
s[i-1]-s[i]>=-h[i]
s[i]-s[i-8]>=r[i](i>8)
s[24]-s[0]>=ans
ans+s[i]-s[i+16]>=r[i](i<=8) 
*/
#include<queue>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1000+100,K=30;
int s[K],r[K],h[K];
struct node
{
    int v,nxt,w;    
}e[N*10];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v=v;e[ejs].w=w;e[ejs].nxt=head[u];head[u]=ejs;
}
int dis[K],vis[K],in[K];
queue<int>q;
int spfa() {
    while(!q.empty())
        q.pop();
    memset(in,0,sizeof(in));
    memset(dis,-0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[0]=0;
    vis[0]=1;
    q.push(0);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=e[i].nxt) {
            int v=e[i].v;
            if(dis[v]<dis[u]+e[i].w) {
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(v);
                    in[v]++;
                    if(in[v]>24) return 0;
                }
            }
        }
    }
    return 1;
}
int work(int ans) {
    ejs=0;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=24;++i) {
        add(i,i-1,-h[i]);
        add(i-1,i,0);
    }
    for(int i=9;i<=24;++i)
        add(i-8,i,r[i]);
    add(0,24,ans);
    add(24,0,-ans);
    for(int i=1;i<=8;++i)
        add(i+16,i,r[i]-ans);
    return spfa();
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--) {
        memset(r,0,sizeof(r));
        memset(h,0,sizeof(h));
        for(int i=1;i<=24;++i)
            cin>>r[i];
        int m;
        cin>>m;
        for(int i=1;i<=m;++i) {
            int x;
            cin>>x;
            h[x+1]++;
        }
        int i;
        for(i=0;i<=m;++i)
            if(work(i)) break;
        if(i<=m) 
        printf("%d\n",i);
        else
            printf("No Solution\n");
    }

    return 0;
}