HDU 4888 Redraw Beautiful Drawings 解題：最大流與唯一性判斷

題目背景

給定一個 n × m 的矩陣，每個儲存格有一個數值。需重新繪製使得每行、每列的和分別等於給定的 a[i]、b[j]，且每個格子的值在 [0, k] 之間。判斷是否有解、解是否唯一，若唯一則輸出解。

網路流建模

• 源點 S 連向每一行節點 i，容量 a[i]。
• 每一行 i 連向每一列 j，容量 k (上限)。
• 每一列 j 連向 匯點 T，容量 b[j]。
• 若最大流 maxflow != sum(a)，則無解 (Impossible)。

唯一性判斷：殘留網路找環

在滿流的殘留網路中，若存在一條從某行節點出發、經由殘留容量 > 0 的邊形成的環，則解不唯一 (Not Unique)。因為沿環增減流量仍滿足約束。使用 DFS 在殘留圖中尋找環 (忽略反向邊避免平凡來回)。

核心程式碼片段 (ISAP 最大流 + DFS 找環)

// ISAP 最大流模板 (略)
// ...

// DFS 判斷殘留網路中是否有環
bool dfs(int u, int fa) {
    if (vis[u]) return true; // 找到環
    vis[u] = true;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (edge[i].cap > 0 && v != fa && dfs(v, u))
            return true;
    }
    vis[u] = false;
    return false;
}

int main() {
    // ... 讀入 n, m, k, 陣列 a, b ...
    // 建圖、跑最大流
    if (maxflow != sum_a) { puts("Impossible"); continue; }
    
    memset(vis, 0, sizeof(vis));
    bool hasCycle = false;
    for (int i = 1; i <= n; ++i)
        if (dfs(i, -1)) { hasCycle = true; break; }
    
    if (hasCycle) puts("Not Unique");
    else {
        puts("Unique");
        // 從殘留邊反推原始流量輸出矩陣
        // flow[i][j] = k - edge.cap (反向邊容量)
    }
}

注意事項

• 節點數：n + m + 2，邊數：n*m + n + m (雙向邊乘 2)。
• ISAP 需正確實作 gap 優化與當前弧優化。
• DFS 找環時需標記訪問狀態 (vis)，回溯時重置，避免誤判。