POJ 1548 Robots（最小路徑覆蓋）
來源：程序員人生 發(fā)布時間：2014-11-11 08:57:12 閱讀次數(shù)：3356次
POJ 1548 Robots
題目鏈接
題意：乍1看還以為是小白上那題dp，其實不是，就是求1共幾個機器人可以覆蓋所有路徑
思路：最小路徑覆蓋問題，1個點如果在另外一個點右下方，就建邊，然后跑最小路徑覆蓋便可
代碼：
#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] == ⑴ || dfs(left[v])) {
left[v] = u;
return true;
}
}
return false;
}
int hungary() {
int ans = 0;
memset(left, ⑴, 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] == ⑴ && y[0] == ⑴) 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
", cnt - hungary());
cnt = 1;
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
