我也忘了题目名字是什么,CSP模拟赛,图论模型构造

mac2026-08-14  6

正题

      每条边的权值是一个区间,表示编号在这个区间内的人可以通过,问选出一条1到n的路径,最多能通过多少人。

      考虑一个答案,当我们把的边加进去之后,1到n是联通的。

       那么就可以枚举左端点,然后按右端点从大到小排个序,依次加入,直到1和n联通,左节点为i点的最大右端点就求出来了,然后更新答案即可。

      代码就不贴了

最新回复(0)