Browse Category

图论

蓝桥杯 城市建设 (Kruskal)

栋栋居住在一个繁华的 C 市中,然而,这个城市的道路大都年久失修。市长准备重新修一些路以方便市民,于是找到了栋栋,希望栋栋能帮助他。
C 市中有 n 个比较重要的地点,市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点,每条道路可以连接其中的两个地点。另外由于 C 市有一条河从中穿过,也可以在其中的一些地点建设码头,所有建了码头的地点可以通过河道连接。
栋栋拿到了允许建设的道路的信息,包括每条可以建设的道路的花费,以及哪些地点可以建设码头和建设码头的花费。
市长希望栋栋给出一个方案,使得任意两个地点能只通过新修的路或者河道互达,同时花费尽量小。

CCF 201712-4 行车路线 (spfa)

小明和小芳出去乡村玩,小明负责开车,小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走,每走1公里小明会增加1的疲劳度。小道不好走,如果连续走小道,小明的疲劳值会快速增加,连续走s公里小明会增加s^2的疲劳度。
现在小芳拿到了地图,请帮助她规划一个开车的路线,使得按这个路线开车小明的疲劳度最小。

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 的最小代价。