2016.9.23二分图考试总结

今日试题

今天是考二分图啊,考场上“觉得”写出来了3道题,考完了发现自己想错了,只有一道题是可以A的,当时我就念了两句诗:苟

啊呸,当时我就吓坏了,心想要被踩穿了。

然而事实上还好,190,rank4。然而我一上午脑袋是晕的啊!!!

看错了一万道题……

第三题看错题了,写了个DP还拿了70分,给跪……

考完了以后也学会了一些新方法,在这里一并总结一下。

  1. 网格图,一行一列只能放一个棋子,对行列分别建点,如果某个格子能放,将代表其所在行列的点间连边。
  2. 网格图一行一列可以分成几段,每段一个棋子,那么久强行多建一些点。
  3. 匈牙利算法倒着来可以得到字典序最小的方案。
  4. 二分图最小点覆盖=最大匹配
  5. DAG最小链覆盖=点数-最大匹配数

还是要多加练习,熟悉算法。

不如来评论一发?