问题描述

Tehran 的一家每天 $24$ 小时营业的超市,需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题——超市在每天的不同时段需要不同数目的出纳员为顾客提供优质服务。他希望雇佣最少数目的出纳员。

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

输入

第一行为测试点的数目 $T$。

对于每组测试数据,第一行为 $24$ 个整数,表示 $R(0),R(1),R(2),⋯ ,R(23)$
接下来一行一个正整数 $N$,表示申请者数目;
接下来 $N$ 行每行一个整数 $t_i$

输出

对于每个测试点,输出一行,包含一个整数,表示需要出纳员的最小数目。如果无解,输出 No Solution

思路

一道差分约束很好的例题。本题思路引用了 这篇 Discuss

首先考虑约束关系。设:$r_i$ 为时间 $i$ 需要的人数
$t_i$ 为时间 $i$ 应聘的人数
$s_i$ 为时间 $i$ 以及之前录用的人数和

那么就存在约束关系:
$s_i-s_{i-8}\geq r_i    (8\leq i\leq 24)$
$s_i-s_{16+i}\geq r_i-s_{24} (1\leq i\leq 7)$
$s_i-s_{i-1}\geq 0    (1\leq i\leq 24)$
$s{i-1}-s_i\geq -t_i   (1\leq i\leq 24)$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 1005
using namespace std;

int T, n, m, cnt, ans, tag[MAXN], need[MAXN], vis[MAXN], head[MAXN], dis[MAXN], num[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];

queue<int> q;

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

bool spfa()
{
    memset(dis, -0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(num, 0, sizeof(num));
    while(!q.empty()) q.pop();

    q.push(0); dis[0]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]<dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                num[to]=num[x]+1;
                if(num[to]>25) return false; 
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
    return true;
}

bool check(int mid)
{
    cnt=0;
    memset(head, 0, sizeof(head));

    for(int i=1; i<=7; i++) addedge(i+16, i, need[i]-mid);
    for(int i=8; i<=24; i++) addedge(i-8, i, need[i]);
    for(int i=1; i<=24; i++)
    {
        addedge(i-1, i, 0);
        addedge(i, i-1, -tag[i]);
    }
    addedge(0, 24, mid);
    return spfa();
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int l=0, r=1000, ans=-1;
        memset(tag, 0, sizeof(tag));

        for(int i=1; i<=24; i++) scanf("%d", &need[i]);
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            int x;
            scanf("%d", &x);
            tag[x+1]++;
        }

        for(int i=0; i<=n; i++)
            if(check(i)) {ans=i; break;}
        if(ans==-1) printf("No Solution\n");
        else printf("%d\n", ans);
    }
}

1 对 “POJ1275 Cashier Employment [差分约束]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注