HDU 4160 Dolls：長方體嵌套與最大匹配

題目大意

給定一組長方體（不可旋轉），若長、寬、高均嚴格遞增，則可嵌套。目標是找出最大嵌套鏈長度，等價於在有向無環圖中求最大匹配數，再用總數減去匹配數得到最小路徑覆蓋。

核心思路

1. 將每個長方體視為圖中的一個節點。
2. 若長方體 i 可嵌套於 j（即 w_i < w_j, l_i < l_j, h_i < h_j），建立有向邊 i → j。
3. 此圖為二分圖，左、右兩部均為所有長方體，邊表示嵌套關係。
4. 求最大匹配，答案 = N - 最大匹配數。

參考代碼（C++）

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 805;
vector<int> G[MAXN];
int match[MAXN];
bool vis[MAXN];
int Nx;

bool dfs(int u) {
    for (int v : G[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxMatching() {
    memset(match, -1, sizeof(match));
    int ans = 0;
    for (int u = 0; u < Nx; ++u) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ++ans;
    }
    return ans;
}

struct Box { int w, l, h; } box[MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%d", &box[i].w, &box[i].l, &box[i].h);
        }
        Nx = n;
        for (int i = 0; i < n; ++i) G[i].clear();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i != j && box[i].w < box[j].w && box[i].l < box[j].l && box[i].h < box[j].h)
                    G[i].push_back(j);
        printf("%d\n", n - maxMatching());
    }
    return 0;
}

複雜度分析

• 建圖：O(N²)
• 匈牙利算法：O(N·E)，此處 E ≤ N²，總體 O(N³)，N ≤ 800 可接受。