Browse Category

图论

POJ 3687 Labeling Balls （拓扑排序）

标号为 1~n 的 N 个球，满足给定的 M 个编号约束关系，输出最终满足关系的球的标号。

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

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

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

有n个模块，每个模块在A上花费ai，在B上花费bi，然后有m个任务(ai,bi,wi)，如果ai,bi不在一起工作的话需要额外花费wi，求最小花费。

给出一张图，求从1到n的最大流。