HDU 4975 矩陣行列和唯一性：最大流 + 矩陣 DP 優化判環

問題建模

給定行和、列和，每格 0-9。判斷是否有解、解是否唯一。
最大流：源點→行（容量=行和），行→列（容量=9），列→匯點（容量=列和）。最大流 = 總和則有解。

唯一性判定優化

殘留網絡有環 ⇔ 解不唯一。
矩陣 DP 判環：ma[i][j] = 殘留網絡中行 i→列 j 的反向流量（即可減少的量）。
若存在 i 使 ma[i][j]>0 && ma[i][k]<9 且另一行 i' 使 ma[i'][j]<9 && ma[i'][k]>0，則可交換構成環。
用 dp[x][y] 記錄列對 (x,y) 是否出現過 ma[*][x]>0 && ma[*][y]<9 的行。

DP 判環代碼

for (i=1; i<=n; i++) if (f[i] && f[i]!=9*m)
    for (j=1; j<=m; j++) if (ff[j] && ff[j]!=9*n)
        for (k=j+1; k<=m; k++) {
            if (ma[i][j]>0 && ma[i][k]<9) { if (dp[k][j]) return 1; dp[j][k]=1; }
            if (ma[i][j]<9 && ma[i][k]>0) { if (dp[j][k]) return 1; dp[k][j]=1; }
        }
return 0;

比 DFS 判環快得多，時間 O(n*m^2) 但常數極小，配合 Dinic 總耗時 156ms。