天天看點

Codeforces Round #639 -E

E

建立有向圖,結點表示變量,a->b表示存在式子(a<b)。

1、 有解的充分必要條件是無環。

無環時一定有解:全部存在性限制,因為無環是以存在入度為零的點,入度為零的點先随意安排一個值,然後按照拓撲序,每個結點安排max(入度結點值)+1即可。

有環時一定無解:有環說明存在一個結點大于或者小于自身,不可能存在限制使其滿足。

又有環無環為對立條件,根據逆反原理,有解時一定無環。

是以定理成立。

2、如果一個結點與比标号小的結點存在<或者>關系,則這個結點隻能為存在性限制。(枚舉證明一下,或者邏輯推導一下。)

其餘的結點可能為任意性限制。則最好情況是其餘節點全部為任意性限制。

令其餘節點都為任意性限制,證明不會出現沖突。

首先,任意性結點之間不存在</>關系,因為存在則任意性結點對不成立。

1) 如果一個存在性結點隻受到一個任意性結點的限制,則存在取值。

2) 如果一個存在性結點受到兩個以上的結點限制,則同時受到<限制,或者>限制,不可能同時受到<和>限制因為這樣會導緻任意性結點之間存在大小關系,則該結點隻需要取max/min(入度結點值)+1/-1即可。

核心思維:數形結合,有向無環圖(DAG)的了解與運用。