题解 CF510E 【Fox And Dinner】

· · 题解

我们考虑一个合法的坐桌子方案。显然环的大小是偶数，又要 $\geq3$，那么 $\geq4$。那么当且仅当每个点的入度出度都为 $1$，并且入出不相等。这个在二分图上就很好建了，等价于每个左部点都有两个不同的出点，每个右部点都有两个不同的入点。那就连边，然后源汇相连的边的容量是 $2$，中间是 $1$。跑最大流，看是否满流。 方案随便构造。