ural1076 Trash(KM)

时间：2010-05-14 来源：chhaya

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

相关阅读更多 +