ural1076 Trash 垃圾

Description
You were just hired as CEO of the local junkyard.One of your jobs is dealing with the incoming trash and sorting it for recycling.The trash comes every day in n containers and each of these containers contains certain amount of each of the n types of trash.Given the amount of trash in the containers find the optimal way to sort the trash.Sorting the trash means putting every type of trash in separate container.Each of the given containers has infinite capacity.The effort for moving one unit of trash from container i to j is 1 if i != j otherwise it is 0.You are to minimize the total effort.
你受聘于当地的垃圾处理公司任CEO，你的一项工作是处理引进的垃圾，以及分类垃圾以进行循环利用。每天，垃圾会有几个集装箱运来，每一个集装箱都包含几种垃圾。给定集装箱里垃圾的数目，请找出最佳的途径去分类这些垃圾。分类垃圾即把每种垃圾分开装到不同的集装箱中。每个集装箱的容量都是无限的。搬动一个单位的垃圾需要耗费代价，从集装箱i到j是1（i<>j,否则代价为0），你必须把代价减到最小。

Input
The first line contains the number n (1 <= n <= 150), the rest of the input file contains the descriptions of the containers.The 1 + i-th line contains the desctiption of the i-th container the j-th amount (0 <= amount <= 100) on this line denotes the amount of the j-th type of trash in the i-th container.
第一行为n(1<=n<=150)，以下为集装箱的情况。第i+1行为第i个集装箱中的j种垃圾的数量amount(0<=amount<=100)。

Output
You should write the minimal effort that is required for sorting the trash.
分类这些垃圾的所需的最小代价。

Sample Input
4
62 41 86 94
73 58 11 12
69 93 89 88
81 40 69 13

Sample Output
650

二分图带权匹配，KM算法，不会的点这里

巴特西

ural1076 Trash 垃圾

最新文章

热门文章