4003

挺牛逼一题。 首先我们发现所有的限制之和相邻的点有关，因此这启发我们进行黑白染色。 染色后不妨设源点向白点连边，黑点向汇点连边，流量为这个点接口的大小。 看上去应该是费用流模型，但是这个费用不好处理。 首先来考虑只有一个接口的，费用是平凡的，只需要让相邻两个为 $1$ ，对面的为 $2$ 即可。 再 ......