0w1

Dinic's

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 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 ]。 問最大輸出總和。…

CFR 513 F. Scaygerboss ( Flow, Binary Search )

Problem - 513F2 - Codeforces題意: 有個 N * M 棋盤,有些格子是障礙。 有一個怪盜,以及 Males 個男生,Females 個女生。 這些人都會用 r, c, t 表示座標位置以及移動一單位距離所需要的時間。 問至少要多少時間,才能使每個人都恰好和一位異性在同一個格…

628F - Bear and Fair Set ( Flow )

Problem - 628F - Codeforces題意: 有人說:他有 N 個數字,範圍在 [ 1, B ]。 他告訴你 Q 個式子,第 i 個為: [ 1, upTo[ i ] ] 之間有 quantity[ i ] 個數字。 除此之外,N 個數字 % 5 == [ 0 .. 4 ] 的數量是相等的。 問是否有可能。制約: 5 ≤ N ≤ B ≤…

CFR 653 D. Delivery Bears ( Flow, Binary Search )

Problem - 653D - Codeforces題意: N 個節點 M 條有向邊的圖。有 X 隻熊。起點 1,終點 N。 這些熊要搬運貨物,如果一隻熊要搬運 W 單位,那麼其他所有熊也必須搬運 W 單位。 每條邊都有限制重量,也就是經過的重量總和不能超過它。 問可以搬運的最大總重量…

CFR 510 E. Fox And Dinner ( Flow )

Problem - 510E - Codeforces題意: 給長度 N 的數列 A[]。要求將每個元素分別放在某個圓桌裡,一個圓桌必須滿足以下條件: 每個元素和兩個元素相鄰。 相鄰元素的和必須是質數。制約: 3 ≤ N ≤ 200 2 ≤ A[ i ] ≤ 1e4解法: 和是質數,那麼偶數一邊,奇數一邊…

CFR 546 E. Soldier and Traveling ( Flow )

Problem - 546E - Codeforces題意: 有 N 個城市,M 條無向邊。 起初第 i 個城市有 A[ i ] 個士兵。 現在進行一次移動,每個士兵都可以選擇不動,或者移動到相鄰的城市。 輸出方案,使得移動後第 i 個城市有 B[ i ] 個士兵。若不存在方案,輸出 -1。制約: 1…

CFR 498 C. Array and Operations ( Flow )

Problem - 498C - Codeforces題意: 給長度為 N 的數列 A[]。 有 M 筆操作: u v:選一個 A[ u ] 和 A[ v ] 的公因數 g,進行 A[ u ] /= g, A[ v ] /= g,保證 ( u + v ) % 2 == 1 問最多能有幾次,你選的公因數 g 不為 1。制約: 2 ≤ N ≤ 100 1 ≤ M ≤ 100 1…

CFR 808 F. Card Game ( Flow, Binary Search )

Problem - 808F - Codeforces題意: 你有 N 張卡。第 i 張卡有 P[ i ] 單位的力量,C[ i ] 單位的魔法性質,L[ i ] 的門檻。 你想組一個總力量不小於 K 單位的牌組,但是這些牌的門檻必須不超過你的等級,並且任意兩張的魔法性質總和不為質數。 你現在的等級…

UVA 11506 - Angry Programmer ( Mincut, Flow )

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