题意： 一条街上有n个大楼，坐标为xi，yi，bi个人在里面工作。 然后防空洞的坐标为pj，qj，可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs（xi - pi） + （yi - qi） + 1。 现在设计了一个避难计划，指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行，所有人避难所用的时间总和是不是最小的。 若是，输出“OPETIMAL",若

JDOJ 2175: 忠诚2 题目传送门 Description 老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的

这道题看似是建图十分简单，实则用裸的最小费用最大流必然会超时，用zkw费用流也会超时。 所以必须看清题意，题目要求只要比当前方案好就行，没说要最好。 那么根据定理，一个费用流是最小费用流的充要条件是这个费用流的残量网络没有负费用圈。对于这个定理，如果不明白可以画一画。 那么对本题来讲，只需要消一次圈就可以找到一个比当前方案好的方案，当然前提是网络中有负圈得情况下。 此时只需沿着负费用圈把各