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

Re:最小割,不会建图的进......................................

Posted by 962861784 at 2011-06-19 10:35:39 on Problem 3469
In Reply To:最小割,不会建图的进...................................... Posted by:962861784 at 2011-06-19 10:34:33
> 将每个任务规约为一个点,添加源汇点s.t,s和每个任务相连,边权为任务在s上处理用的时间;
> 每个任务和t相连,边权为任务在t上处理用的时间.对于(a,b,w),连两条边(a,b,w)和(b,a,w);
> 为什么最小割就是解呢?
> 由最小割的定义,点基被分成两部分S.T,S为源点能到达的点的集合,其余点构成T;
> 再来看此题,假如s和a之间的边是割,那么a在s上被处理,否则a在t上被处理,s能到达的点在t上处理,其余点在s上处理;

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