给定一个地图，含字符 ‘*’ ‘#’ ‘o’，然后战舰只能放置在字符 ∗ <script id="MathJax-Element-50" type="math/tex">*</script>上面，且一行或一列不能同时放置两个战舰，除非中间间隔有字符#，问最多能放置多少个战舰？
1.就是一个二分图匹配，听说是陈题，但是觉得建图方式比较特别，所以mark一下，主要是理解一下建图的过程！
2.首先缩点一下，就是同一行或者同一列，如果中间没有字符#，说明这个块只能放置一个战舰，所以被视为一个点。对同一行而言，缩点完成后，可以称之为X部；对同一列而言，缩点完成后，可以称之为Y部；
3.考虑放置一个战舰，那么战舰的坐标位置必定有其行坐标和列坐标，也就是X部中必定有一个点，Y部中也必定有一个点，所以放置一个战舰的过程就可以理解为X部与Y部顶点连了一条边，毫无疑问每个点最多只能连一条边，因为这个点内只能放置一个战舰！
4.所以问题就转化为了求最大边集(一条边表示放置了一个战舰)，也就是求二分图的最大匹配！
本文发布于:2024-01-27 22:00:06，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/17063640052887.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
