BZOJ5335 : [TJOI2018]智力竞赛

二分答案，转化成求最少的路径，覆盖住所有权值$\leq mid$的点。 建立二分图，若$i$的后继为$j$，则连边$i\rightarrow j$，求出最大匹配，则点数减去最大匹配数即为最少需要的路径数量。 特别地如果某个点$i$的权值$>mid$，则它可以不经过，连边$i\rightarrow i
posted @ 2018-08-26 04:06  Claris  阅读(712)  评论(0)  编辑  收藏  举报