#include #include #include #include #include #include using namespace std; typedef pair 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 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 */ 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; }