Browse Category

图论

POJ 3159 Candies （差分约束）

n个人在一起分糖果，给出m组约束，a、b、c 代表b比a多分的糖果不能超过c个，然后求第n个人比第1个最多多多少个糖果。

用一个7位的string代表一个编号，两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号衍生出来，代价是这两个编号之间相应的distance，现在要找出一个衍生方案，使得所有的编号之间都可以直接或者间接形成转换，并且总代价最小，也就是distance之和最小。

一个矩形中，有N个城市（*），现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。

问至少需要放置多少个基站才能使得所有的城市都覆盖无线？

给出所有障碍物的坐标，每一次可以消灭一行或者一列，问最少需要几次才可以消灭完所有的障碍物。

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

依序给出一些字母之间的大小关系，判断并输出它能否唯一确定一个序列满足这一关系。