撤退计划(ZJOI1153　evacuate plan )
   

　　城市里有若干座市政大厦和一些在核战争时用于躲藏市政工作人员的核辐射掩体。每一座核辐射掩体在战争期间的供给能力是有一定的容量，仅够供给一定数目人的需要，而且没有任何多余的供给。理论上讲，所有从给定一些市政大厦中的工作人员，要跑向最近的掩体。但是，这将导致在同一时刻，一些掩体容纳过多的人，而一些掩体又是一半都是空的。

　　为了解决这个问题，市议会制定了一个特殊的撤退方案。他们并不是将每个工作人员单独指定给某一掩体，而是将掩体指派给市政大厦，方案列出每座大厦中要使用某个掩体的工作人员数目，而具体的指派任务，则由大厦的管理者负责。撤退方案考虑到每座大厦中的众多工作人员，所有工作人员必须指定到掩体中。同时每个掩体的供给能力有限，被指定到每个掩体中的人数不能超过它的供给能力。尽管可能有些掩体不会被完全使用。

　　市议会认为他们的计划是最优的，即所有工作人员到达各自被指定去掩体的时间和最小。但市长总是不太相信议会的能力，他请你做为一个独立的顾问来检验这个撤退计划。你的任务是确定这个计划的确是最优的，或证明存在另外一个更优的撤退计划，来证明市议会的无能。

　　在你任务最初的收集要求时，你可以发现城市可以用网格表示。市政大厦和掩体的位置用两个整数表示，位于(Xi, Yi) 的大厦到位于(Pj, Qj)的掩体的时间为Di,j = |Xi - Pj| + |Yi - Qj| + 1 分钟。

　　输入：

　　输入文件包含城市的描述和撤退计划的描述。输入文件的第一行包含两个整数N和M (中间有一空格)。 N (1 ≤ N ≤ 100) 是城市中市政大厦的数目，大厦的编号从1到N。M (1 ≤ M ≤ 100) 是城市中掩体的数目，掩体的编号从1到M。

　　接下来N行描述市政大厦。每行包含三个整数Xi, Yi 和Bi （中间有一个空格隔开），这里Xi, Yi (-1000 ≤ Xi, Yi ≤ 1000) 是大厦的坐标，Bi (1 ≤ Bi ≤ 1000)是这座大厦中的工作人员的数目。

　　再下来M行描述城市中的掩体。每行包含三个整数Pj, Qj和Cj （两数中间有一个空格），这里Pi, Qi (-1000 ≤ Pj, Qj ≤ 1000) 是一座掩体的坐标，Cj (1 ≤ Cj ≤ 1000)是该掩体的供给能力。

　　最后的N行表示市议会的撤退计划。每行表示一座大厦的撤退计划（按城市的描述中的顺序给出）。计划的第i座大厦包含M个整数Ei,j，之间被空格隔开。Ei,j (0 ≤ Ei,j ≤ 1000)是从第i座大厦必须撤退到第j座掩体的人数。

　　输入文件中的撤退计划绝对是合法的，不要判错。

　　输出:

　　如果议会的计划是最优的，则输出"OPTIMAL"，否则在输出文件的第一行输出"SUBOPTIMAL"，然后按输入文件中的同样格式输出N行，表示你的计划。你的计划本身不必是最优的，但它必须是合法且优于市议会的方案。

　　Sample inputs and outputs

　　　　　　　　　　　　　

　　下面是一个如上图所示的样例输入输出，图中大厦用Bx表示，掩体用Sx表示。括号中的数表示大厦中的人数或掩体的能力。

　　evacuate.in 　　　　　　　　　　　evacuate.out
　　3 4　　　　　　　　　　　　　　　　　　SUBOPTIMAL
　　-3 3 5　　　　　　　　　　　　　　　　　3 0 1 1
　　-2 -2 6　　　　　　　　　　　　　　　　 0 0 6 0
　　2 2 5　　　　　　　　　　　　　　　　　 0 4 0 1
　　-1 1 3　　　　　　　　　　
　　1 1 4
　　-2 -2 7
　　0 -1 3
　　3 1 1 0
　　0 0 6 0
　　0 3 0 2
　　3 4　　　　　　　　　　　　　　　　　　　OPTIMAL
　　-3 3 5
　　-2 -2 6
　　2 2 5
　　-1 1 3
　　1 1 4
　　-2 -2 7
　　0 -1 3
　　3 0 1 1
　　0 0 6 0
　　0 4 0 1
　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有