题解 P2762 【太空飞行计划问题】

· · 题解

这里大概讲一下转换成最大流以后怎么输出。

一个结论就是假如我们跑的是 Dinic 那么我们最后一次网络流（这一次网络流并没有起任何作用，只是确认了无更多残余流量可以退出了。）中所有被分到层的都一定被选上了。

没有更多残余流量其实意味着这个图已经被割成了两部分，一个实验如果有层数意味着它没有被割掉（被选上了），一个仪器如果有层数意味着它已经被割掉了（也是被选上了）。

于是只要在最后输出所有有层数的点就行了。