【BZOJ2879】【NOI2012】美食节

新费用流建图技巧get

显然可以把每个厨师拆成\(\sum p\)个跑费用流

但是(你们又不高兴)这样跑会很慢,那怎么办?

开始只设\(m\)个厨师表示该厨师最后一次做的菜,增广完将被增广的厨师新建一个点作为他倒数第二次做的菜,代价翻倍,以此类推

脑补一下是对的

说点什么

  Subscribe  
提醒