\(POJ\) \(1548\) \(Robots\)
题意
相当于给出\(N\)个坐标点，因为机器人只能向下或者向右走，所以如果能到达其他点，则连接这两个点，即line[i][j]=1
最小路径覆盖数:
对于一个\(DAG\)（有向无环图），选取最少条路径，使得每个 顶点属于且仅属于一条路径。路径长度可以为零；（有向图中找一些路径，使之覆盖了图中的所有顶点，就是任意一个顶点都跟那些路径中的某一条关联，且任何一个顶点有且只有一个与之关联）
最小路径覆盖数（最少边覆盖）=顶点数-最大匹配数；
思路：把每个点都拆成两个点，分为入点和出点，如果 \(u\) 到 \(v\) 有边，那么我们就让 \(u\) 的入点连向 \(v\) 的出点 ， 匈牙利算出最大匹配。
解答：
最小路径覆盖的话非常简单，这题显然可以转化为\(DAG\)。要注意类似\(floyd\)求传递闭包的办法，排序后把符合条件的全部建边！
不过也可以使用\(LIS\)，运用\(dilworth\)定理，也就是求最长反链的长度。也就是求最长下降子数列的长度
二分图建边+匈牙利算法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
// 链式前向星
const int N = 1010, M = N * N;
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
// 匈牙利算法
int st[N], match[N];
int dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v] == 1) continue;
st[v] = 1;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return 1;
}
}
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ1548.in", "r", stdin);
#endif
int a, b;
while (true) {
// 初始化匈牙利算法的数组
memset(match, -1, sizeof match);
memset(st, 0, sizeof st);
// 初始化链式前向星
memset(h, -1, sizeof h);
idx = 0;
vector<PII> vec;
while (true) {
cin >> a >> b;
if (a == 0 && b == 0) break;
if (a == -1 && b == -1) exit(0);
vec.push_back(make_pair(a, b)); // POJ太老了，我喜欢用vec.push_back({a,b});但它不认识
}
// 按x1<=x2,y1<=y2逻辑进行排序
// 总结：给了一大堆点，我们需要按一定顺序进行排序，然后再枚举遍历。一般的排序办法就是PII的默认排序办法
sort(vec.begin(), vec.end());
/* 每个机器人可以从左->右，上->下,走完就废。
我们上面进行了排序，是按x1<=x2,y1<=y2排序的，但可能出现(x2>x1,y2<y1)的情况，也就是后面的行，但列在前面
这是不符合题意的，不能连边，需要判断一下,即y要非单调上升，也就是y2>=y1
*/
for (int i = 0; i < vec.size(); i++)
for (int j = i + 1; j < vec.size(); j++)
if (vec[j].y >= vec[i].y) add(i, j);
// 记录哪个点有出边,这个建边，是不是类似于floyd求传递闭包？多么痛的领悟！
// 匈牙利算法
int res = 0;
/* 注意：这里需要枚举的上限是vec.size()!原因是上面我们建边时用的是add(i,j),也就是在链式前向星中保存的是原始点集中的点号！一开始黄海错误的把下面的循环终止条件写成了i<=idx,结果TLE，这是不对的！有两个原因：
① 因为除非你在建图时使用了离散化，否则点号不全！！因为有的点号因为不符合vec[j].y>=vec[i].y的条件，也就是在
下一行的左侧，被排除掉了，但它的号被占着呢！
② idx是边数，不是点数，SB到家了！
我又写了一个离散化后的版本，但代码太长了，不好玩，不如直接枚举vec.size()来的快，这样，即使有的点不符合条件，也就没有出边，不影响结果！
代码短的多！
*/
for (int i = 0; i < vec.size(); i++) {
memset(st, 0, sizeof st);
if (dfs(i)) res++;
}
// 最小路径覆盖数 = 节点总数 - 最大匹配数
printf("%d\n", vec.size() - res);
}
return 0;
}
离散化后的版本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010, M = N * N;
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int st[N], match[N];
int dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v] == 1) continue;
st[v] = 1;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return 1;
}
}
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ1548.in", "r", stdin);
#endif
int a, b;
while (true) {
memset(match, -1, sizeof match);
memset(st, 0, sizeof st);
memset(h, -1, sizeof h);
idx = 0;
vector<PII> vec;
while (true) {
cin >> a >> b;
if (a == 0 && b == 0) break;
if (a == -1 && b == -1) exit(0);
vec.push_back(make_pair(a, b));
}
sort(vec.begin(), vec.end());
vector<int> alls; // 存储所有待离散化的值
for (int i = 0; i < vec.size(); i++)
for (int j = i + 1; j < vec.size(); j++)
if (vec[j].y >= vec[i].y) alls.push_back(i), alls.push_back(j);
// 将所有值排序
sort(alls.begin(), alls.end());
// 去掉重复元素
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 重新捋着建边，通过二分查找，找出新的序号，这样就可以使用i<=alls.size()了！
for (int i = 0; i < vec.size(); i++)
for (int j = i + 1; j < vec.size(); j++)
if (vec[j].y >= vec[i].y) {
int x = lower_bound(alls.begin(), alls.end(), i) - alls.begin();
int y = lower_bound(alls.begin(), alls.end(), j) - alls.begin();
add(x, y);
}
int res = 0;
for (int i = 0; i < alls.size(); i++) {
// 最开始黄海SB的以为二分后，这里可以使用i<idx做为终止条件，其实是SB到家了！idx是边数，是边数，是边数！
// 不是点数，不是点数，不是点数！
memset(st, 0, sizeof st);
if (dfs(i)) res++;
}
printf("%d\n", vec.size() - res);
}
return 0;
}
\(LIS+Dilworth\)定理
其实也可以用\(LIS\)来解决。把所有点按第一关键字\(x\)，第二关键字\(y\)从小到大排序。
则从\(1\sim n\)的点已经满足了第一维，从\(i->j(i< j)\)只需要满足\(a[i].y<=a[j].y\)即可。
例如样例就是\(4 \ 4 \ 6 \ 4 \ 7\).根据题意，这个偏序集的链是一个不降序列。
我们现在就是要求这个偏序集的最小链划分数（也就是图中的最小链覆盖数），
根据\(Dilworth\)定理，也就是求最长反链的长度。也就是求最长下降子数列的长度。可以\(dp\)解决。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 600;
int ans, f[N];
PII a[N];
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ1548.in", "r", stdin);
#endif
while (true) {
memset(f, 0, sizeof f);
ans = 0;
int al = 0;
while (true) {
int x, y;
scanf("%d %d", &x, &y);
if (x == -1) exit(0);
if (x == 0) break;
a[al++] = make_pair(x, y);
}
sort(a, a + al);
// LIS
for (int i = 0; i < al; i++)
for (int j = 0; j < i; j++)
if (a[j].y > a[i].y) f[i] = max(f[i], f[j] + 1);
// Dilworth
for (int i = 0; i < al; i++) ans = max(ans, f[i]);
printf("%d\n", ans + 1);
}
return 0;
}