题目描述(ID:12055)
标题: 捉迷藏(最小路径覆盖)
标签: 图结构 二分图
详情:
  小a和小b在一片树林里捉迷藏……
  这片树林里有N座房子,M条有向道路,组成了一张有向无环图。
  树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。如果从房子A沿着路走下去能够到达B,那么在A和B里的人是能够相互望见的。
  现在小b要在这N座房子里选择K座作为藏身点,同时小a也专挑小b作为藏身点的房子进去寻找,为了避免被小a看见,小b要求这K个藏身点的任意两个之间都没有路径相连。
  为了让小a更难找到自己,小b想知道最多能选出多少个藏身点?
输入格式:
  第一行两个整数N,M。
  接下来M行每行两个整数x、y,表示一条从x到y的有向道路。
输出格式:
  一个整数K,表示最多能选取的藏身点个数。
提示: 类型:二分图最小路径覆盖、floyd传递闭包

首先对读入的有向图做传递闭包,然后求最小路径覆盖即可。最小路径覆盖数=n-最大匹配。

具体证明参见CTSC2008 river 第一问或者Violet4 travel。

传递闭包+二分匹配 时间 O(N^3) 空间 O(N^2)
限制:   对于20% 的数据,N≤10,M<=20。
  对于60% 的数据, N≤100,M<=1000。
  对于100% 的数据,N≤200,M<=30000,1<=x,y<=N。
样例:

输入

4 4
1 2
3 2
3 4
4 2

输出

2
登录并解答