主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
POJ.3041 Asteroids
最后更新于 2025-08-28 09:09:54
作者
2huk
分类
题解
题解
P3041
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
> 给定一个网格，网格上有敌人，每次可以同时消灭某一行或某一列上的所有敌人。求消灭所有敌人需要的最小操作次数。 我们将每个敌人的所在行与所在边连边，问题转化成： > 在图中选择最少的点，使得每条边的两个端点中至少有一个被选择。 这是最小点覆盖。而最小点覆盖等于最大匹配，所以直接 dinic 做完了。
正在渲染内容...
点赞
0
收藏
0
