poj1275 cashier-employment

因为题目问的是至少要招几个人，那我们就从小到大枚举要招几个人，看是否合法。

输入need表示这一小时至少需要工作的人数，然后用h存一下这一小时最多可以开始工作的人数（就是输入时可以达到的合法的工作人数）。所以每个小时开始工作的人数一定在0到h之间。所以可以考虑用每个小时开始工作的人作为差分变量。

但是还有一个限制：一个人只工作8个小时，所以对于某个点，从他开始前8个点开始工作的人数的和必须>=need

因为差分约束需要a-b>=c的形式，所以我们需要一个前缀和表示从1-i小时开始工作的总人数，相减可以得到每个小时工作的人数。用这个前缀和作为差分变量。

还有一个条件，因为我们枚举找了几个人，所以总人数不能超过所枚举数。

#include using namespace std;
const int maxn=10005;
int T,m,h[maxn],need[maxn];//某一时刻来应聘的人数 
int v[maxn],w[maxn],head[maxn],nxt[maxn];
int s=24,inque[maxn],dis[maxn];
queue q;int N=0;
void add_edge(int x,int y,int z)
{N++;v[N]=y;w[N]=z;nxt[N]=head[x];head[x]=N;
}
int solve(int sum)
{N=0;memset(head,-1,sizeof(head));add_edge(24,0,0);add_edge(0,24,-h[0]);add_edge(24,23,sum);for(int i=1;i<=23;i++) add_edge(i-1,i,0);for(int i=1;i<=23;i++) add_edge(i,i-1,-h[i]);for(int i=8;i<=23;i++) add_edge(i-8,i,need[i]);for(int i=0;i<8;i++) add_edge(i+16,i,need[i]-sum);memset(dis,-0x3f,sizeof(dis));memset(inque,0,sizeof(inque));while(!q.empty()) q.pop();q.push(s);inque[s]=1;dis[s]=0;int num=0;while(!q.empty()){int x=q.front();q.pop();inque[x]=0;for(int i=head[x];i!=-1;i=nxt[i]){if(dis[v[i]]=1000) return 0;}}if(dis[23]==sum) return 1;return 0;
}
void work()
{memset(h,0,sizeof(h)); N=0;memset(head,-1,sizeof(head));for(int i=0;i<=23;i++) scanf("%d",&need[i]);scanf("%d",&m); for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！