POJ 1548 Robots(最小路径覆盖)
路径 最小 poj 覆盖 robots
2023-09-14 09:06:18 时间
POJ 1548 Robots
题意:乍一看还以为是小白上那题dp,事实上不是,就是求一共几个机器人能够覆盖全部路径
思路:最小路径覆盖问题。一个点假设在还有一个点右下方,就建边。然后跑最小路径覆盖就可以
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 25 * 25; int x[N], y[N], cnt = 1; vector<int> g[N]; bool judge(int i, int j) { return x[j] >= x[i] && y[j] >= y[i]; } int left[N], vis[N]; bool dfs(int u) { for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (vis[v]) continue; vis[v] = 1; if (left[v] == -1 || dfs(left[v])) { left[v] = u; return true; } } return false; } int hungary() { int ans = 0; memset(left, -1, sizeof(left)); for (int i = 0; i < cnt; i++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ans++; } return ans; } int main() { while (~scanf("%d%d", &x[0], &y[0])) { if (x[0] == -1 && y[0] == -1) break; while (~scanf("%d%d", &x[cnt], &y[cnt])) { if (x[cnt] == 0 && y[cnt] == 0) break; cnt++; } for (int i = 0; i < cnt; i++) { g[i].clear(); for (int j = 0; j < i; j++) { if (judge(i, j)) g[i].push_back(j); if (judge(j, i)) g[j].push_back(i); } } printf("%d\n", cnt - hungary()); cnt = 1; } return 0; }
相关文章
- 如何查看python源码_python判断路径是否存在
- 120. 三角形最小路径和
- leetcode刷题(124)——64. 最小路径和
- istio-in-action - 05 VirtualService 使用路径匹配重写路由
- RHEL/CentOS网络相关的配置文件路径详解程序员
- Java获取当前类路径详解编程语言
- Linux下妙用复制文件:轻松找到文件路径(linux复制文件路径)
- Linux 系统路径文件:掌握路径的重要性(linux系统路径文件)
- Linux库搜索路径探索(linux库搜索路径)
- 载基于c语言与MySQL数据库的图片路径下载方案(c mysql图片路径下)
- MySQL安装路径缺失解决方法(mysql不显示安装路径)
- 取图片路径的正则
- Oracle10g各个帐号的访问权限、登录路径、监控状态命令查询等等