Codeforces Round #192 (Div. 2)

A. Cakeminator

• 每行每列都判断是否有障碍。

---

B. Road Construction

• (m<frac{n}{2})，必然有一个点没有连边。

---

C. Purification

• 若每一行都能找到空格，即可覆盖全图。
• 否则至少有一行全是障碍，此时每一列都需要找到空格才能覆盖全图。

---

D. Biridian Forest

• 以出口为起点，计算其余点到出口的最短距离。
• (0-9)的最短距离小于等于主角的最短距离，则可以在出口拦住主角。

---

E. Graph Reconstruction

• 对于(nle7)，最多有(frac{6*7}{2}=21)条边，暴力找即可。
• 对于(ngt7)的情况，由于度最大为2，也就是原图有若干条链和环构成。假设有一条链为(a_1a_2a_3a_4a_5a_6a_7)，我们重构为(a_1a_3a_5a_7a_2a_4a_6)，重构的图形无论成链还是都不会利用原图的边。注意4个点的情况，会形成(a_1a_3a_2a_4)，2-3是原图存在的边，所以最后交换前两个元素。最后得到若干序列，则两两插空构新序列即可。