POJ 1548 Robots（最小路径覆盖）

本文主要是介绍POJ 1548 Robots（最小路径覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}

这篇关于POJ 1548 Robots（最小路径覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---