題目大意
n×m矩陣，每個格子有數字。一人可走k次，每次從未訪問格子出發，每步可向右/下跳躍到任意未訪問格子。移動(a,b)→(c,d)消耗能量|c-a|+|d-b|-1；若兩格數字相同，獲得該數字能量。初始能量0，問k次能否覆蓋所有格子（每格恰一次），若能輸出最大剩餘能量。
核心建模：最小路徑覆蓋 → 費用流
- 最小路徑覆蓋：DAG中最小路徑覆蓋 = 頂點數 - 最大匹配數。本題移動只能右/下，構成DAG。若最小路徑覆蓋數 > k，則無法覆蓋，輸出-1。
- 最大權路徑覆蓋：需在滿足覆蓋的前提下最大化總能量（獲得-消耗）。轉化為最小費用最大流：
- 每個格子拆分為左部X、右部Y（X→Y容量1費用0）。
- 可達邊：X_i → Y_j 容量1，費用 = 消耗能量 - 獲得能量（取負後求最小費用即最大化收益）。
- 源點S連所有X，容量1費用0；所有Y連匯點T，容量1費用0。
- 關鍵：S再連一個中間節點T1，容量k費用0；T1連所有Y，容量1費用大常數M（如10000），保證優先走k條路徑覆蓋所有點，剩餘流量走T1→Y補齊匹配。
- 跑滿流量n*m的最小費用流，若不可行輸出-1；否則總費用扣除n*m*M後取負即為最大剩餘能量。
費用計算細節
- 移動消耗：|Δx|+|Δy|-1。
- 數字相同獎勵：+digit。
- 邊費用 = 消耗 - 獎勵。為避免負費用干擾SPFA，統一加大常數M（10000），最終答案 = -(總費用 - n*m*M)。
代碼關鍵片段
總結
本題將「k條路徑覆蓋所有點且最大化收益」轉化為帶容量限制的最小費用流。關鍵技巧：虛擬節點T1限制路徑數、大常數M轉化最大權為最小費用、拆點構建二分圖。模板級費用流代碼配合精巧建模即可AC。
