Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

CSAcademy 25. Zone Capture ( BCC )

Round #25 (Div. 2 only)題意: 給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。制約: 1 ≤ N, M ≤ 1000解法: 將…

CFR Educational 10 E. Pursuit For Artifacts ( Bridge BCC + Shrink Cycle )

http://codeforces.com/contest/652/problem/E Shrink each bridge BCC to as a single vertex. If a treasure exists in some BCC, that BCC will be sure able to take that treasure. Otherwise a treasure might be on a bridge linking BCCs, and we wi…

UVA 1108 Mining Your Own Business ( 點雙連通分量 )

題目的圖論模型是要求將儘量少的點標記,使得刪除任意一點後每個聯通分量有至少一個被標記的點。 我們要發現一般來說標記在割點上不會比較好,而且在同一個點雙連通分量上標記兩個以上的點是無意義的。再說如果一個點雙連通分量含兩個以上的割點,我們可以不…

Biconnected Components

A vertex biconnected component (bcc) can be defined as a connected component (cc) that is still a cc after any vertex is plucked out of the graph, and usually we would think about the bcc as the largest component that satisfies. An edge bc…