ZOJ 3792 Romantic Value 解題：最小割與割邊計數

題目大意

無向圖，邊有權值 (浪漫值)。需刪除一些邊使 s、t 不連通。優先最小化刪除邊權值和 (即最小割)，次優先最小化刪除邊數量。輸出 (總權值 - 最小割權值) / 割邊數量。

核心觀察

1. 最小割 = 最大流：標準最大流 (Dinic/ISAP) 求得最小割權值 minCut。
2. 求最小割邊數量：在殘留網路中，飽和邊 (流量 = 容量) 為割邊候選。但需找出「最小割」中邊數最少的那一組。
   • 方法一 (雙重最大流)：將殘留網路中流量 = 0 的邊容量設為 1，其他設為 INF，源匯點不變，再跑一次最大流。得到的流值即為最小割邊數 cnt。
   • 方法二 (容量縮放)：原圖邊容量改為 cap * C + 1 (C 足夠大，如 10000)。跑一次最大流，maxflow / C = minCut，maxflow % C = cnt。

程式碼實作 (方法一)

// 第一次最大流 (Dinic)
int maxflow1 = dinic(s, t);
if (maxflow1 == 0) { puts("Inf"); continue; } // 原本不連通

// 構建第二層圖：殘留網路中 cap==0 的邊(割邊候選)設容量1，其餘 INF
for (int i=0; i