Posted on 2010-10-07 18:50
成幸毅 阅读(526)
评论(0) 编辑 收藏 引用
题目连接：
http://poj.org/problem?id=3498 带点容量限制的做法是拆点，把一个点拆成两个点，他们直接连一条边就是点容量。然后再求最大流。
此题的做法是把每个ice floe拆成两个点i,和i'，他们之间连一条边为可跳跃次数，原点连接每个ice floe的i，容量为每个ice floe上企鹅的个数，然后根据企鹅的跳跃与坐标位置见图，如果企鹅可从i题floe i 跳到 floe j, 则i'向j连一条无穷大的边，j‘向i连一条无穷大的边，然后枚举汇点，建立一个汇点，然后用枚举的floe i和汇点连一条无穷大的边，这里要注意，不需要每次去重新见图，直接删除添加与汇点连接的那条边就好，邻接表不知道怎么完成删除一条边，用邻接矩阵就可以了。到此建模完成，直接流。代码就不贴了。