A new Graph Game：最小費用流判斷哈密頓環

A new Graph Game - 最小費用流求最短子環

題意：給定 N 個節點的無向圖，M 條邊及邊長。判斷是否存在包含所有節點的環（哈密頓環），若存在輸出最短環長，否則 "NO"。

建模為最小費用最大流

• 每個節點拆分為左側 (1..N) 和右側 (N+1..2N)。
• 源點 S(0) → 左側節點：容量 1，費用 0。
• 右側節點 → 匯點 T(2N+1)：容量 1，費用 0。
• 原圖邊 (x, y, w) → 左側 x → 右側 y：容量 1，費用 w（雙向加兩條）。
• 跑最小費用最大流，若最大流 < N，說明無法完美匹配，輸出 "NO"；否則最小費用即為最短環長。

原理：每個節點必須有一條入邊和一條出邊，構成若干環；最小費用流會傾向於合併成一個大環（若圖連通），費用即為環長總和。

SPFA + Dinic 風格實現

struct Edge { int to, next, cap, flow, cost; };
bool spfa(int s, int t) { /* 最短路分層 */ }
struct Node { int f, c; } minCostMaxflow(int s, int t, int &cost) { /* 增廣 */ }

關鍵點

1. 節點拆分將「每點入度=出度=1」轉化為二分圖完美匹配。
2. 最小費用流保證總長度最小。
3. 邊權預處理：同一點對多條邊保留最小權。
4. 複雜度：O(flow × SPFA) ≈ O(N × M)，N≤1000，M≤100000，可接受。

完整代碼框架

見原文，包含 init, addedge, spfa, minCostMaxflow, 主函數讀入多測試用例、建圖、輸出結果。