Browse Category

图论

POJ 3308 Paratroopers (最小割)

n×m 的地图,给出 L 个火星人登陆的坐标,要在火星人登陆地球的瞬间全部消灭他们,有一种激光枪,一次可以消灭一行(或一列),消灭一行(或一列)有不同的代价,总代价是所有激光枪的代价之积,求最小的总代价。

POJ 2195 Going Home (最小费用最大流)

给出一张地图, . 是空地, H 是房子, m 是小人,并且地图上有相同数量的房子与小人,每个小人每次只能横向或者纵向移动一格,求最终所有人都找到一间独立的房子所走的步数。

POJ 1364 King (差分约束)

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