ural1076 Trash(KM)
时间：2010-05-14 来源：chhaya
http://acm.timus.ru/problem.aspx?space=1&num=1076
题意：n个垃圾筒，每个里面有n种垃圾， 现在要把垃圾归类， 分别放在不同的垃圾桶里（正好n个垃圾桶n种垃圾）， 问至少要移动多少数量的垃圾到其他垃圾桶去。
分析：先求每个垃圾桶留哪种垃圾，留的就是不用移动的，统计一共不用移动多少， 再把所有的垃圾量减去那个数目就行了。经典的二分图的最大权匹配。 KM算法搞定。
题意：n个垃圾筒，每个里面有n种垃圾， 现在要把垃圾归类， 分别放在不同的垃圾桶里（正好n个垃圾桶n种垃圾）， 问至少要移动多少数量的垃圾到其他垃圾桶去。
分析：先求每个垃圾桶留哪种垃圾，留的就是不用移动的，统计一共不用移动多少， 再把所有的垃圾量减去那个数目就行了。经典的二分图的最大权匹配。 KM算法搞定。
相关阅读 更多 +
