0w1

Matching

CFR 316 C. Tidying Up ( MCMF )

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

Yuki 421 しろくろチョコレート ( Greedy, Maximum Bipartite Matching )

No.421 しろくろチョコレート - yukicoder題意: 有一個 N * M 的黑白交接的棋盤巧克力。有些已經被吃掉了,用 '.' 表示。你每吃一片 1 * 2 的巧克力會得到幸福值 100,每吃不相鄰的一塊黑色和一塊白色會得到幸福值 10,隨便吃一塊會得到幸福值 1,問最大幸…

GCJ 2017 Qual D. Fashion Show ( Bipartite Matching )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 給 N * N 的棋盤,以及一些士兵。士兵有三種 : { 'x', '+', 'o' },若沒有士兵用 '.' 描述。一個格子至多一個士兵。士兵配置的規則如下: 1. 任意兩個在同個水平或鉛直線上的士兵,必須有其中…

CSAcademy 23 E. No Prime Sum ( Bipartite Matching, Minimum Vertex Cover )

Round #23 (Div. 2 only)題意: 給 N 個相異正整數,問最少要移除幾個數字,能使任意兩個數字的和不為質數。輸出方案。限制: 2≤N≤2000 The elements of S are distinct integers between 1 and 10^5解法: 首先顯然偶數+偶數以及奇數+奇數的情形一定不會產…

POI 2 Stage 2 Board Covering ( Bipartite Matching )

http://main.edu.pl/en/archive/oi/2/sza題意: 給一個 N * N 的棋盤,X, Y, Z 三塊為不用覆蓋的,求是否可以用 2 * 1 ( 可旋轉 ) 的東西覆蓋滿棋盤,可以的話輸出方案。資料規模: In the only line of the standard input there are written four numbers …