0w1

Mincut

ARC 074 F - Lotus Leaves ( Flow, Mincut )

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder題意: H * W 的棋盤。 起點 S,終點 T。這兩個點都有葉子。 其他葉子用 'o' 描述。 每次可以選擇同行或同列的 'o' 移動到那裡。 問最少要移除多少葉子才能使 S 不能到達 T。無解輸出 -1。制約: 2≤…

CFR 62 E. World Evil ( Flow, Mincut, DP, bitmask )

Problem - 62E - Codeforces題意: 給一個多角形柱體形成的網路,問最大流是多少。 起點是上面的面的所有點,匯點是下面的面的所有點。制約: 2 ≤ N ≤ 5 2 ≤ M ≤ 1e5 解法: 顯然不能暴力跑網路流算法。 考慮用 dp 求解。 最大流不好求,求最小割。 考慮水平…

CFR 434 D. Nanami's Power Plant ( Flow, Mincut )

Problem - 434D - Codeforces題意: 有 N 個二次函數,以及 M 條不等式。 你想要最大化所有二次函數的輸出的總和。 對於第 i 個二次函數,參數範圍是 [ L[ i ], R[ i ] ] 的整數。 第 i 條不等式表示 X[ U[ i ] ] ≤ X[ V[ i ] ] + D[ i ]。 問最大輸出總和。…

UVA 11506 - Angry Programmer ( Mincut, Flow )

UVa Online Judge題意: 有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。制約: 2 ≤ 節點數( M ) ≤ 50, 0 ≤ 網路線數( W ) ≤ 1000 0 ≤ 容量 ≤…