Browse Tag

图论

POJ 3026 Borg Maze (最小生成树)

从 S 出发,去到达每一个 A ,求最小的总路径长度,空格是空地,# 是墙,并且在走的过程中我们可以在 S 或 A 点分裂,也就是从该点可以延伸出多条路径到其他点,但是每一次只能让其中的一个继续行走。

HDU 3394 Railway (点双联通分量+桥)

公园有n个景点,管理员计划要建m条道路,并且安排一些形成回路的参观路径,如果一条道路可以被多条回路共用,那么这条边是冲突边,如果一个块中有多个环,则该块中的每条边都是冲突边。
如果不能形成环的路则为不需要的边,求无向图中冲突边与不需要边的个数。

POJ 1459 Power Network (最大流)

给出一些发电站,一些消费站与一些转发站,再给各个传送线的传电能力,求消耗站能获得的最大电量是多少。

POJ 1273:Drainage Ditches (最大流)

下雨的时候约翰的田里总是积水,积水淹没了他种的三叶草,于是他做了若干条排水沟,每条沟在起始处安置一个阀门来控制这条沟的最大排水量,现在给出沟的条数以及阀门的个数,并给出每条沟的最大排水量,求在处理积水时的最大排出量。