春分++
题意
有 $n$ 个人和 $m$ 个物品,每个人需要使用每个物品一次。
然而,每个人和每个物品上都带有病毒,所有病毒两两不同。发生直接接触时,一边的所有病毒就会传播到另一边。
不过,人与物品接触时可以使用若干个隔离装置。每个隔离装置有 $A,B$ 两面,若使用了 $1,2,\ldots,n$ 这 $n$ 个隔离装置,则人只与 $1A$ 直接接触,物品只与 $nB$ 直接接触,而 $iB$ 和 $(i+1)A$ 也发生了直接接触。隔离装置可以自由翻面(即同一装置的 $A,B$ 可以在整个过程中途互换)。
为了保证整个过程结束后所有人和物体没有被传播新的病毒,求:
隔离装置数量 $K$ 的一个下界 $K_{\text{min}}(n,m)$;
构造一个 $K\leq K_{\text{min}}(n,m)+C$ 的方案,其中 $C$ 为常数。