Browse Tag

图论

POJ 2516 Minimum Cost （最小费用最大流）

有n个店主，k个物品，m个供应商，求满足店主需求所需要的最小花费。

假设当前有这样一个序列 S={a1,a2,a3…an} ，现在给出一些不等式，使得 a[i]+a[i+1]+a[i+2]+…+a[i+n]k[i] ，问这样的一个序列是否存在。

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

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

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

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

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