Luogu 2762 – 太空飞行计划问题

链接:Luogu 2762 – 太空飞行计划问题

最大权闭合子图,收入(实验)为正点权,支出(仪器)为负点权。正点权连接到s,负点权连接到t,容量为点权的绝对值。

最大收益是正点权之和减去最小割。这一点很好理解,就是对于每个实验,要么放弃收入(不做实验),要么有所投入(做实验买仪器的成本)。

输出方案是在最终的分层图中看与s和t相连的点。(这个输出方法还没有理解)

输出时还可以考虑和s联通的点。(学长说的)

坑点:需要注意的是每次bfs分层的时候要把d数组清零。

 

说点什么

avatar
50
  Subscribe  
提醒