0w1

MCMF

HE Zulu and Alarm Clock ( MCMF )

https://www.hackerearth.com/problem/algorithm/zulu-and-alarm-clock-1/題意: T 筆測資。 N 個鬧鐘,K 個時間。 你要把 K 個鬧鐘調成這 K 個時間。 你可以上下調整時、秒、分,會進位退位。 問最小調整次數。制約: 1≤T≤2 1≤N≤50 1≤K≤17解法: 可以用遮罩…

CFR 491 C. Deciphering ( MCMF )

Problem - 491C - Codeforces題意: 給你長度 N 的字串 A 以及字串 B。 你可以做一組字母對字母的一對一映射,使得同位置相符的字符數量最多。制約: 1 ≤ N ≤ 2e6 1 ≤ K ≤ 52解法: MCMF 亂流。 映射前映射後。 源點建弧到映射前的容量是 1,費用是映射前的…

CFR 739 E. Gosha is hunting ( MCMF )

Problem - 739E - Codeforces題意: 你有 A 個普通球,B 個超級球。 有 N 隻神奇寶貝。 對於第 i 隻神奇寶貝,如果用普通球,抓到的機率是 P[ i ]; 如果用超級球,抓到的機率是 U[ i ]。 對於同一隻神奇寶貝,兩種球都只能至多丟一次。 問最佳策略下,期望可…

CFR 362 E. Petya and Pipes ( MCMF, Binary Search )

Problem - 362E - Codeforces題意: 有 N 個節點,以及有向弧,用鄰接矩陣表示。 若 C[ i ][ j ] = 0,代表 ( i, j ) 之間沒有弧。 源點 1,匯點 N。 對於一個弧,可以花費一單位的金子增加一單位流量。 你有 K 單位的金子,問最大流量。制約: 2 ≤ N ≤ 50 0…

CFR 717 G. Underfail ( MCMF )

Problem - 717G - Codeforces題意: 給長度 N 的字串 T。 有 M 種字串 S[],如果把第 i 個字串疊在 T 的上面重合,可以得到 P[ i ] 分。 對於 T 的所有位置,都不能有超過 X 個字符疊在上面。 問最大總得分。制約: 1 ≤ N ≤ 500 1 ≤ M ≤ 100 1 ≤ P[ i ] ≤ 10…

CFR 164 C. Machine Programming ( MCMF )

Problem - 164C - Codeforces題意: 你有 K 個機器,可以獨立處理任務。 你有 N 個任務可以選擇接或不接。 任務 i 需要在 [ S[ i ], T[ i ] ) 期間佔用一個機器,價值為 C[ i ]。 問最大總價值。制約: 1 ≤ N ≤ 1000 1 ≤ K ≤ 50 1 ≤ S[ i ], T[ i ] ≤ 1e9 1 …

CFR 316 C. Tidying Up ( MCMF )

Problem - 316C2 - Codeforces題意: 給一個 N * M 的矩陣,裡面有 N * M 個數字,[ 1, N * M / 2 ] 各出現兩次。 問最少要將幾個格子裡的數字移位,才能使得存在一種匹配,每個匹配都是相鄰的兩格子,且內容相同。制約: 2 ≤ N * M ≤ 80解法: 用最大流保證…

CFR 237 E. Build String ( MCMF )

Problem - 237E - Codeforces題意: 你有一個目標字串 T。 你有 N 個字串。 如果你拿第 i 個字串裡面的某個字符,每拿一個花費 A[ i ]。 拿掉的字符不能再拿。 問總花費。無法則輸出 -1。制約: 1 ≤ N ≤ 100 0 ≤ A[ i ] ≤ 100解法: MCMF 隨便流。 把 T 拆成…

CFR 277 E. Binary Tree on Plane ( MCMF )

Problem - 277E - Codeforces題意: 有 N 個點在二維整數坐標上。 要求做一個二叉樹。 一個點 i 可以作為點 j 的父親,若且唯若 Y[ i ] > Y[ j ]。 問最小的邊長總和。若無解輸出 -1。制約: 2 ≤ N ≤ 400 abs( X[ i ] ), abs( Y[ i ] ) ≤ 1000 所有點相異 容…

CFR 730 I. Olympiad in Programming and Sports ( MCMF )

Problem - 730I - Codeforces題意: 有兩個屋子,容量分別為 P, S。 有 N 個人,他們會各自選擇一個屋子進去。 第 i 個人對屋子 A 的喜好度是 A[ i ],對屋子 B 的喜好度是 B[ i ]。 輸出方案,使得滿意程度 ( 選擇的屋子的喜好度 ) 總和最大。制約: 2 ≤ N …