POJ – 2594 – Treasure Exploration (floyd传递闭包+最小路径覆盖)

题目链接:POJ - 2594 题目大意: 有n个点,m个有向边,用机器人探索这些点,机器人可以从任意的一点开始延路径前进,但不可返回。 问最少需要多少个机器人访问到所有的点。 题目分析: 这个题可以转换到图上的最小路径覆盖问题。 引用: 最小路径覆盖(path covering):是“路径” 覆盖…

POJ – 3041 – Cable master (二分图匹配入门,最小顶点覆盖)

题目链接:POJ - 1064 题目大意: 有一个N*N的图,图中一些点有障碍物,有一种武器,一次可以摧毁一行或者一列的障碍物, 问最少需要多少次,能把所有障碍物清除干净。 题目分析: 对于每个坐标点,建立一个行对应列的边,然后进行二分图匹配。 已知最大匹配数=最小顶点覆盖(最小顶点覆盖要求用最少的…

POJ – 1486 – Sorting Slides (二分匹配的唯一边)

题目链接:POJ - 2594  题目大意: 故纸堆:桌上有n张幻灯片杂乱地叠在一起,给出每张幻灯片的边界和页码坐标,求在不翻动的情况下哪些页码可以确定? 页码可能在保护页码坐标的任意一张幻灯片上 题目分析: 二分图找唯一匹配的边,即删除该边之后无法形成完美匹配。 首先见图找到一个完美匹配…

POJ – 3020 – Antenna Placement (二分图最小路径覆盖)

题目链接:POJ - 3020 题目大意: 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。 每个基站只能覆盖所在点已经他相邻的一个点(或上或左或下或右)问至少放置多少个基站才能使得所有的城市都覆盖无线? 题目分析: 这是一个二分图的最小路…