题面

题意

在一个神奇的公司，该公司有 $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;
}