【bzoj3389】[Usaco2004 Dec]Cleaning Shifts安排值班

2014年10月1日1,5423

Description

    一天有T(1≤T≤10^6)个时段.约翰正打算安排他的N(1≤N≤25000)只奶牛来值班,打扫
打扫牛棚卫生.每只奶牛都有自己的空闲时间段[Si,Ei](1≤Si≤Ei≤T),只能把空闲的奶牛安排出来值班.而且,每个时间段必需有奶牛在值班.  那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出-1.

Input

    第1行:N,T.
    第2到N+1行:Si,Ei.

Output

    最少安排的奶牛数.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2
样例说明
奶牛1和奶牛3参与值班即可.

题解

同遭遇战可以转换为最短路。。。

 

 

  • Chenyao2014年10月4日 下午3:34 回复

    最短路做法太神了,Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

    #1  
  • 黄润泽2016年8月2日 下午6:33 回复

    为啥SPFA会TLE?

    #2  
    • hzwer2016年8月5日 下午5:00 回复
      admin

      spfa上界是nm的

      #21