【题意】：给出n个箱子，每个箱子有三个值w,l,h。如果一个箱子的这三个值严格小于另一个箱子的三个值，那么可以把这个箱子放在另一个箱子里面。每个箱子里面最多只能放一个箱子，问最小情况下还有多少个箱子。
【题解】：一开始直接上排序加贪心，然后发现有明显的bug。
考虑排序后dp，发现是个2d的最长上升子序列，不过难以实现。
无奈之下请教3x，原来是个经典问题，最小路径覆盖。
最小路径覆盖在二分图上满足：最小路径覆盖 = 顶点数 - 最大匹配。
由于原图不是二分图，需实行转换，只需拆点即可。
最后直接上匈牙利即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 1500
19 #define maxm 1000500
20 int n;
21 int eh[maxn], tot;
22 bool visit[maxn];
23 int match[maxn];
24
25 struct Edge {
26 int u, v, next;
27 }et[maxm];
28
29 struct Point {
30 int w, l, h;
31 }p[maxn];
32
33 void init() {
34 tot = 0;
35 memset(eh, -1, sizeof(eh));
36 }
37
38 void addedge(int u, int v) {
39 Edge e = {u, v, eh[u]};
40 et[tot] = e;
41 eh[u] = tot++;
42 }
43
44 bool dfs(int u) {
45 for(int i = eh[u]; i != -1; i = et[i].next) {
46 int v = et[i].v;
47 if (!visit[v]) {
48 visit[v] = true;
49 if (match[v] == -1 || dfs(match[v])) {
50 match[v] = u;
51 return true;
52 }
53 }
54 }
55 return false;
56 }
57
58 int Match() {//二分图匹配
59 int cnt = 0;
60 memset(match, -1, sizeof (match));
61 for (int u = 1; u <= 2 * n; u++) {
62 memset(visit, false, sizeof (visit));
63 if (dfs(u)) cnt++; //每找到一条增广路，匹配数+1
64 }
65 return cnt; //返回最大匹配数
66 }
67
68 bool check(const Point &a, const Point &b) {
69 return a.h < b.h && a.l < b.l && a.w < b.w;
70 }
71
72 void build() {
73 init();
74 for(int i = 0; i < n; i++) {
75 for(int j = 0; j < n; j++) {
76 if(check(p[i], p[j])) addedge(i + n, j);
77 }
78 }
79 }
80
81 int main() {
82 while(~scanf("%d", &n) && n) {
83 for(int i = 0; i < n; i++) scanf("%d%d%d", &p[i].w, &p[i].l, &p[i].h);
84 build();
85 printf("%d\n", n - Match());
86 }
87 return 0;
88 }