LG2823 时间表

发布于 2021-06-26  3.5k 次阅读


题面

题意

在一个神奇的公司,该公司有 $P$ 名员工,一个星期有 $D$ 天,每天有 $H$ 小时。

每名员工在每一个小时都在做一件事:工作,开会,或者休息。员工在一段时间内的工作时间为该员工在这段时间内进行“工作”事件和“开会”事件的小时数。每个员工每周进行“工作”事件的时间不能超过 $L_i$ 小时,每个员工每天总工作时间不可超过 $N$ 小时。

现在公司已经为每位用户确定好了“开会”事件发生的时间,用 $F_{k,i,j}$ 表示,$F_{k,i,j}=0$ 表示 $k$ 号员工在第 $i$ 天的第 $j$ 小时需要进行“开会”事件,$F_{k,i,j}=1$ 表示 $k$ 号员工在第 $i$ 天的第 $j$ 小时可以选择进行“工作”或者“休息”事件。

由于公司业务要求,每周的第 $i$ 天的第 $j$ 小时需要有正好 $R_{i,j}$ 人在进行“工作”事件。

该公司还有午休事件,为每一天的 $L_{T_{begin}} \sim L_{T_{end}}$ 小时段。每名员工在该时间段内都必须要有至少一个小时在进行“休息”事件。

现将所有的条件告诉你,需要你求出是否存在一种员工的时间分配方案(即为每个员工指定每天的每一小时在进行的事件类型)满足所有的限制条件。如果有这样的方案输出 Yes,否则输出 No

分析

题面相当恶臭,各类限制条件的关系也挺复杂的,但思维难度并不高。因此该题考察的是语文水平。

由于题目中的限制都是在对时间区间内的工作时间进行限制,考虑网络流,将“工作”事件时间作为流量,按题意模拟建图即可。

先建立源点 $S$ 与汇点 $T$,接下来考虑每一个限制条件。

  1. 每个员工每周最多进行“工作”事件 $L_i$ 小时:建立 $P$ 个点 $A_i$,约束第 $i$ 个员工的每周工作时间。从 $S$ 向每个 $A_i$ 连一条流量为 $L_i$ 的边即可。
  2. 每个员工每天最多工作 $N$ 小时:建立 $D \times P$ 个点 $B_{i,j}$,约束第 $i$ 个员工在第 $j$ 天的工作时间。从 $A_i$ 向每个 $B_{i,j}$ 连一条流量为 $N-\sum_{k=1}^{H} [F_{i,j,k}=0]$ 的边即可。(因为第 $j$ 天已有一些时间必须要进行“开会”事件)
  3. 每个员工午休时间需要有至少一个小时进行“休息”事件:建立 $D \times P$ 个点 $C_{i,j}$,约束第 $i$ 个员工在第 $j$ 天的午休时间段内的工作时间。从每个 $B_{i,j}$ 向 $C_{i,j}$ 连一条流量为 $L_{T_{end}}-L_{T_{begin}}-\sum_{k=1}^{H} [F_{i,j,k}=0]$ 的边即可(该边流量为午休时间段内能进行的最长的“工作”事件的总时间 $-1$)。
  4. 考虑工作分配的方案:建立 $D \times H$ 个点 $E_{i,j}$ 约束第 $i$ 天第 $j$ 小时总的进行“工作”事件的人数。从 $C_{i,j}$ 或 $D_{i,j}$(取决于是否在休息时间)向每个满足 $F_{i,j,k}=1$ 的 $k$ 对应的 $E_{j,k}$ 连一条流量为 $1$ 的边。
  5. 第 $i$ 天的第 $j$ 小时需要有正好 $R_{i,j}$ 人进行“工作”事件:从 $E_{i,j}$ 向 $T$ 连一条流量为 $R_{i,j}$ 的边即可。

最后跑最大流,如果最大流等于 $\sum_{i=1}^{D} \sum_{j=1}^{H} R_{i,j}$ 且中途没有建立过负权边则说明存在合法方案。

(说中途没有建立过负权边是因为在第 $2$ 步和第 $3$ 步的建图过程中边权可能小于零,原因是强制指定的开会时间已经超过员工每日工作时长的限制,则显然不存在合法方案)

代码

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {

// fread

}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

template <size_t maxn>
class Dinic {

// Dinic

};

#define INF 0x3f3f3f3f3f3f3f3f
#define maxn 75

Dinic<20005> dinic;

int f[maxn][maxn], g[maxn][maxn];

int main() {
    int _ = read<int>();
    while (_--) {
        int P = read<int>(), D = read<int>(), H = read<int>(), N = read<int>();
        int S = P + 2 * P * D + D * H + 1, T = S + 1;
        dinic.INIT(T);
        for (register int i = 1; i <= P; i++) dinic.addEdge(S, i, read<int>());
        int tl = read<int>(), tr = read<int>();
        long long tot = 0;
        for (register int i = 1; i <= D; i++)
            for (register int j = 1, t; j <= H; j++)
                dinic.addEdge(P + 2 * P * D + (i - 1) * H + j, T, t = read<int>()), tot += t;
        for (register int k = 1; k <= P; k++)
            for (register int i = 1; i <= D; i++) {
                f[k][i] = g[k][i] = 0;
                for (register int j = 1; j <= H; j++)
                    if (read<int>()) {
                        if (tl <= j && j <= tr)
                            dinic.addEdge(P + P * D + (k - 1) * D + i, P + 2 * P * D + (i - 1) * H + j, 1), g[k][i]++;
                        else
                            dinic.addEdge(P + (k - 1) * D + i, P + 2 * P * D + (i - 1) * H + j, 1);
                    } else
                        f[k][i]++;
            }
        bool flag = false;
        for (register int i = 1; i <= P; i++)
            for (register int j = 1; j <= D; j++) {
                dinic.addEdge(i, P + (i - 1) * D + j, N - f[i][j]);
                if (N - f[i][j] < 0) flag = true;
            }
        for (register int i = 1; i <= P; i++)
            for (register int j = 1; j <= D; j++) {
                dinic.addEdge(P + (i - 1) * D + j, P + P * D + (i - 1) * D + j, g[i][j] - 1);
                if (g[i][j] - 1 < 0) flag = true;
            }
        putstr((!flag && dinic.maxFlow(S, T) == tot) ? "Yes" : "No"), putch('\n');
    }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话