HDU 1565 方格取數：最大權獨立集 = 總和 - 最小割 (網絡流)

問題描述

n×n 方格，每格有權值。選取若干格子使任兩格不相鄰（不共邊），最大化權值和。即**最大權獨立集**問題。

核心轉化：二分圖最大權獨立集 = 總權 - 最小割

1. 棋盤染色：將格子按 (i+j)%2 分為黑/白兩集合，構成二分圖（相鄰格顏色不同）。
2. 建流網絡：
   • 源點 S 連向黑格，容量 = 格子權值。
   • 白格連向匯點 T，容量 = 格子權值。
   • 黑格向相鄰白格連邊，容量 = INF（足夠大，如 1e9）。
3. 最大流 = 最小割。割邊意義：割斷 S→黑格 表示不選該黑格（損失其權值）；割斷 白格→T 表示不選該白格。INF 邊不會被割（代價太大），保證不同時選相鄰格子。
4. 最大權獨立集 = 總權值和 - 最小割值 = 總權值和 - 最大流值。

關鍵代碼片段 (Dinic 算法)

struct Dinic {
    struct Edge { int to, cap, rev; };
    vector> G;
    vector level, it;
    Dinic(int n) : G(n), level(n), it(n) {}
    void addEdge(int fr, int to, int cap) {
        G[fr].push_back({to, cap, (int)G[to].size()});
        G[to].push_back({fr, 0, (int)G[fr].size()-1});
    }
    bool bfs(int s, int t) { /* 標準 BFS 分層 */ }
    int dfs(int v, int t, int f) { /* 標準 DFS 增廣 */ }
    int maxFlow(int s, int t) { /* 循環 BFS+DFS */ }
};

// 主程序建圖
int id(int i, int j) { return (i-1)*n + j; } // 1-based 編號
Dinic dinic(n*n + 2);
int S = 0, T = n*n + 1;
for (int i=1; i<=n; ++i)
  for (int j=1; j<=n; ++j) {
    int u = id(i,j);
    if ((i+j)%2 == 1) { // 黑格
        dinic.addEdge(S, u, a[i][j]);
        for (int d=0; d<4; ++d) {
            int ni=i+dx[d], nj=j+dy[d];
            if (1<=ni&&ni<=n && 1<=nj&&nj<=n)
                dinic.addEdge(u, id(ni,nj), INF);
        }
    } else { // 白格
        dinic.addEdge(u, T, a[i][j]);
    }
    sum += a[i][j];
  }
cout << sum - dinic.maxFlow(S, T) << endl;

關鍵細節

• 單向邊：只從黑向白連 INF 邊，避免產生環導致錯誤。
• INF 取值：大於總權值和即可（如 1e9）。
• 多測試用例：每案例重新初始化 Dinic。

複雜度

• 節點數 ≤ 20×20+2 = 402，邊數 ≤ 4×400 = 1600。
• Dinic 在此規模極快，輕鬆通過。

總結

HDU 1565 是「最大權獨立集 → 最小割」經典建模。棋盤染色構造二分圖、源匯點連權值、相鄰點連 INF 邊，是解決網格圖選取問題的標準套路（如 POJ 2411、HDU 3572）。