给定一个DAG 可以用n+1条路径覆盖求不能覆盖的点中最小值最大

出题人的语文水平+elijahqi的语文水平为负无穷 读错题只有10分系列

考虑二分答案 然后二分图匹配 求最小可相交路径覆盖问题

注意二分答案的单调性 即 若3->6之间有一个8 然而这次二分的答案是7 他们这条边也应该视为存在

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论