| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一个构图思路:1、设0为源点,n+1为汇点 2、源点和每个猪圈的第1个顾客连边,边的权是开始时猪圈中猪的数目 3、若源点和某节点之间有重边,则将权合并(因此源点流出的流量就是所有的猪圈能提供的猪的数量) 4、顾客j紧跟在顾客i之后打开某个猪圈,则边<i,j>的权是INF,因为如果顾客j紧跟在顾客i之后打开某个猪圈,那么就有可能根据顾客j的需要将其他猪圈中的猪调整到该猪圈,这样顾客j就能买到尽可能多的猪。 5、每个顾客和汇点之间连边,边的权值是顾客希望购买的猪的数目(因此汇点的流入量就是每个顾客说购买的猪的数目) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator