Browse Category

图论

Codeforces 876 E. National Property (2-SAT)

现在我们想要让所有行的字典序升序排列,且对于每一种数字,我们可以采用一种变换,比如 x->x' ,所有加 ' 的都比不加小,问是否可以找到一种变换使得原序列升序。

HDU 5988 Coding Contest (最小费用流)

有 n 个区域,每个区域都有一些人和食物,区域之间存在 m 条有向路径,每条路都有一个人数上限。路径之间铺了电线,每当有人通过时都会有 pi 的概率碰到它,但是第一个通过的人一定不会碰到,求所有人都获取到食物而碰到电线的最小概率。

51nod 1693 水群 (spfa)

当前有一个数 x ,操作 1 是 x = x × k ,代价为 k ;操作 2 是 x = x - 1 ,代价为 1 ,求从 1 到 n 的最小代价。

POJ 3683 Priest John’s Busiest Day (2-SAT)

一个小镇里面只有一个牧师,现在有些新人要结婚,需要牧师分别去主持一个仪式,给出每对新人婚礼的开始时间 s 和结束时间 t ,还有他们俩的这个仪式需要的时间(每对新人需要的时间长短可能不同) d ,牧师可以在婚礼开始的时间 d 内(s 到 s+d)或者是结束前的时间 d 内(t - d 到 t)完成这个仪式。现在问能否给出一种安排,让牧师能完成所有夫妇婚礼的仪式,如果可以,输出一种安排。