将每个任务规约为一个点,添加源汇点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上处理,其余点在t上处理;

• Re:最小割,不会建图的进...................................... (229) 962861784 2011-06-19 10:35:39
  • Re:最小割,不会建图的进...................................... (0) msg888msg 2012-02-29 15:57:37