Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一个构图思路:

Posted by braisure at 2020-06-02 17:25:25 on Problem 1149
1、设0为源点,n+1为汇点
2、源点和每个猪圈的第1个顾客连边,边的权是开始时猪圈中猪的数目
3、若源点和某节点之间有重边,则将权合并(因此源点流出的流量就是所有的猪圈能提供的猪的数量)
4、顾客j紧跟在顾客i之后打开某个猪圈,则边<i,j>的权是INF,因为如果顾客j紧跟在顾客i之后打开某个猪圈,那么就有可能根据顾客j的需要将其他猪圈中的猪调整到该猪圈,这样顾客j就能买到尽可能多的猪。
5、每个顾客和汇点之间连边,边的权值是顾客希望购买的猪的数目(因此汇点的流入量就是每个顾客说购买的猪的数目)

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator