【題意】：給出n個箱子，每個箱子有三個值w,l,h。如果一個箱子的這三個值嚴格小于另一個箱子的三個值，那么可以把這個箱子放在另一個箱子里面。每個箱子里面最多只能放一個箱子，問最小情況下還有多少個箱子。

【題解】：一開始直接上排序加貪心，然后發(fā)現(xiàn)有明顯的bug。
               考慮排序后dp，發(fā)現(xiàn)是個2d的最長上升子序列，不過難以實現(xiàn)。
               無奈之下請教3x，原來是個經(jīng)典問題，最小路徑覆蓋。
               最小路徑覆蓋在二分圖上滿足：最小路徑覆蓋 = 頂點數(shù) - 最大匹配。
               由于原圖不是二分圖，需實行轉(zhuǎn)換，只需拆點即可。
               最后直接上匈牙利即可。

【代碼】：
  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++; //每找到一條增廣路，匹配數(shù)+1
 64     }
 65     return cnt; //返回最大匹配數(shù)
 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 }