【bzoj1930】[Shoi2003]pacman吃豆豆

2014年6月14日3,0639

Description

两个PACMAN吃豆豆。一开始的时候,PACMAN都在坐标原点的左下方,豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪,只能向右走或者向上走,他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下,他们俩加起来最多能吃掉多少豆豆。

Input

第一行为一个整数N,表示豆豆的数目。 接下来 N 行,每行一对正整数,表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。

Output

仅有一行包含一个整数,即两个PACMAN加起来最多能吃掉的豆豆数量

Sample Input

8
8 1
1 5
5 7
2 2
7 8
4 6
3 3
6 4

Sample Output

7

HINT

N < = 2000

题解

最后一个点卡spfa费用流。。。再加上本机跑得慢才过了7个点。。。

什么时候再想想dp做法。。。

费用流就是拆点随便搞

 

  • skydec2014年7月7日 下午1:16 回复

    这都能过!跪大神!

    #1  
    • hzwer2014年7月7日 下午3:35 回复
      admin

      没过啊

      #11
      • 黑暗世界2014年7月7日 下午9:56 回复

        你手动第一次增广就能过了

        #12
        • ju_ruo2014年7月8日 下午2:05 回复

          这种无聊题简直了

          #13
  • lyx2015年3月12日 上午11:51 回复

    我一开始自己去写这道题,交上去TLE(很奇怪的是内存0kb,时间0ms),交了总共7次都是这样。。。一怒之下试了一下学长的代码。。。结果剧情相同。。。我对自己这种遭遇感到醉了

    #2  
  • huanghongxun2015年4月26日 下午2:10 回复

    记得用优先栈就过了。。

    #3  
  • NaApe2016年2月23日 下午8:03 回复

    其实这题建边时加个剪枝貌似就不会MLE了

    #4  
    • hzwer2016年3月6日 上午12:42 回复
      admin

      原来如此,我还以为一定要手动增广当时就懒得写了

      #41
  • aaaaa2017年1月22日 下午4:58 回复

    此题需要优化连边,暴力连边会TLE

    #5