HDU 5076 最小割靈活運用 - 二分圖建模與網絡流解法詳解

HDU 5076 最小割靈活運用 - 二分圖建模與網絡流解法詳解

題目大意

給定 n 位二進制數對應的節點，每個節點必須選擇兩個值 A（小於閾值的最大值）或 B（大於等於閾值的最大值）之一。若兩個節點滿足：

1. 二進制表示僅有一位不同（即漢明距離為 1）
2. 至少有一個節點選擇了 B 值

則可獲得額外加成 (ui ^ uj)。求最大總收益並輸出具體選擇方案。

核心建模思路：最小割 = 總權重 - 最大收益

採用「選取所有權重，再割掉最小代價」的經典最小割模型：

• 將每個節點拆分為兩個點，中間連容量為 INF 的邊，強制二選一
• 根據二進制中 1 的個數奇偶性分層：奇數層連源點，偶數層連匯點（或相反）
• 漢明距離為 1 的點對之間連邊，容量為加成值 (ui ^ uj)
• 源點/匯點到節點的邊容量分別為 A、B 值

關鍵洞察：奇偶分層將「同側選擇 A 值無法獲得加成」的約束轉化為割邊，完美契合最小割模型。

關鍵代碼片段 (Dinic 算法)

struct Edge { int to, cap, rev; };
vector G[MAXN];
int level[MAXN], iter[MAXN];

void add_edge(int from, int to, int cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size() - 1});
}

void bfs(int s) {
    fill(level, level + N, -1);
    queue q; level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v]) if (e.cap > 0 && level[e.to] < 0) {
            level[e.to] = level[v] + 1; q.push(e.to);
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); i++) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0, INF_FLOW = 1e9;
    while (true) {
        bfs(s); if (level[t] < 0) return flow;
        fill(iter, iter + N, 0);
        int f; while ((f = dfs(s, t, INF_FLOW)) > 0) flow += f;
    }
}

建圖邏輯詳解

void build() {
    for (int i = 0; i < nn; i++) {
        add_edge(i + 1, i + nn + 1, INF);  // 拆點，強制二選一
        
        if (popcount(i) & 1) {  // 奇數層
            add_edge(S, i + 1, a[i][low[i]]);      // S -> A值
            add_edge(i + nn + 1, T, a[i][high[i]]); // B值 -> T
            for (int j = 0; j < nn; j++) 
                if (popcount(i ^ j) == 1)  // 漢明距離為1
                    add_edge(i + 1, j + nn + 1, ui[i] ^ ui[j]);
        } else {  // 偶數層，反向連接
            add_edge(i + nn + 1, T, a[i][low[i]]);
            add_edge(S, i + 1, a[i][high[i]]);
        }
    }
}

方案恢復

跑完最大流後，從源點出發在殘量網絡中 DFS/BFS 可達的節點屬於 S 集合，不可達屬於 T 集合。根據節點所屬集合及奇偶性決定選 low 還是 high。

處理負數權重技巧

所有權值先加 1024 變非負，最終答案 = 總權和 - 最小割 - n * 1024。