分发百奇 2

子任务1 设空格数为$K$，枚举$2^K$种分配并检查每名学生是否得到两种口味。时间复杂度为$O(2^K NM)$。

完整解法 为每行和每列建立一个顶点；每个空格$(i,j)$对应连接行$i$与列$j$的一条边。横向盒子对应将边指向行顶点，纵向盒子对应指向列顶点。将含有学生的行、列对应的顶点称为必需顶点。目标等价于让所有必需顶点的入度为正。

在树连通分量中，边数比顶点数少一。若所有顶点都必需，则不可能满足要求。否则选一个非必需顶点作为根，将树边全部指向子节点，根以外的每个顶点都有入边。

若连通分量有环，取一棵生成树及一条非树边$(r,c)$。以$r$为根，将树边指向子节点，并将选定的非树边指向$r$。这样所有顶点都有入边，其余边可任意定向。孤立顶点也适用同一树分量判定。

因此，当且仅当存在全部顶点都必需的树分量时无解。用并查集建立生成森林并收集非树边，选根后迭代遍历构造答案。时间复杂度为$O(NM\alpha(N+M))$，空间复杂度为$O(NM+N+M)$。

Solution written by GPT6.1