这题数据是不是太小了
查看原帖
这题数据是不是太小了
26199
wenjing233楼主2023/3/30 23:14

看到一篇题解这样写

关于求方案,由于n,m只有50,我们可以考虑枚举删除器材和t之间的边,如果删去后的最大流和原来的最大流的差值等于这条边的边权,那么这条边就是必须满流的,也就是这个器材是必要的。再根据需要的器材我们容易知道要做的实验有哪些。

额,复杂度爆炸且不优美,有一说一,明明只要在dinic分层的时候记录一下哪些点和S割在一块就好了。

2023/3/30 23:14
加载中...