CERC 2010 J - Justice for All

題目: Construct a bipartite graph with at most 200 vertex at each side that has exactly N (1 ≤ N ≤ 10⁶) perfect matching

如果想要一個有 k 個 perfect matching 的 graph, 可以使用 k 個 vertex construct 到
方法是 l[1] 連到 r[1], r[2].. r[k], 然後 l[i] 連到 r[1] 和 r[i]
fix 了 l[1] 的 match vertex 便 fix 了整個 matching

想要一個有 N 個 perfect matching 的 graph, 可以把 N factorize, 然後把上述的 subgraph disjoint union 一起
當然如果 N 有很大的 prime factor 便會使得 vertex 數目超出限制
既然 x 不足夠, 就要想方法去 implement + operation

例如, 把 N 分解成 Sum{2^m}
首先要 construct 一個有 2^m 個 perfect matching 的 connected subgraph
使用 m+1 個 vertex, 加上 edge {(l[i], r[j]): i ≤ m, j ≤ i+1}

為了做到 +, 我們希望每個 subgraph 都有兩種 'mode': 1 個 matching 以及 2^m 個 matching
並且每次有 exactly 一個 subgraph 是使用後者的 mode
因此, 便想到再新增一個 'control vertex'
一個 subgraph 的第 m+1 個 node match 到這個 control vertex 的話, 便可以有 2^m 個 matching
否則只有一種

因此, 只要在每個 subgraph 的 l[m+1] 連到 r[1] 及 control vertex
如果連到 control vertex 的話便可以有 2^m 個 matching
否則 l[i] 的 matching 數目便會 reduce 為 1 個
就可以砌到任意數目的 perfect matching