这道题我居然想出来了。。只有11个人AC哎。。好激动。。
一下就看出可以用有上下界的最小费用可行流。。
就是对增加的处理有些BT。。
每个人分开讨论
如果把来了看成+号，走了看成-号。。那么对于相邻的两个。。
1++。。中间肯定要加个-。。
2+-。。可以不加。。也可以在中间加-+。。
3–。。中间肯定要加个+。。
当然可以狂加+-+-+-之类的。。但是可以看成一个新人来简化问题。。
于是分别处理以上三种情况。。具体太繁琐。。简单说一下。。
1和3好处理。。加个顶点就OK了。。
2很BT。。要加2个顶点。。我想了半天突然明悟了。。。
新人的话只需要用容量无限费用为1的边就可以了。。
不过我不会写有上下界的最小费用可行流。。无语。。。
去学学再去AC这题吧。。。
N不大时间应该够。。
P.S似乎运用了网络流中配“零件”的思想。。配“零件”。。真好玩。。。