Detail of message

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

第一个最大流的正式AC啊。。还是一次AC...给和我一样弱弱的人一点提示。。

Posted by Sona at 2008-09-25 21:13:30 on Problem 3436

制造一个0为源点，2*n+1为汇点。。
剩下的把每个机器（节点）分解成两个点(i,i+n)，这两个点之间最大流量即为Performance。。
其他可用的边流量都是无穷大，记得1-n的点只能进，n+1-2*n的点只能出。。。
例如：机器i的完成品可用到j上加工  maxflow[i+n][j]=MAXINT。。。
然后朴素最大流。。。用邻接矩阵+BFS，最傻的方法,16ms。。。
祝大家最大流愉快！

Followed by:

Re:第一个最大流的正式AC啊。。还是一次AC...给和我一样弱弱的人一点提示。。 (242) archerstarlee 2009-03-27 16:07:35
Re:第一个最大流的正式AC啊。。还是一次AC...给和我一样弱弱的人一点提示。。 (6) sheeper 2012-12-09 00:42:05

Post your reply here:

Home Page Go Back To top