Going Home

分类: IT文章 • 2025-01-19 17:23:31

题目大意：在一个网格里面有n个小男人和n个房子，现在想让每个小男人都有一个房子住，不过每个人移动一下都需要花费￥1，现在求出来最小的总花费。ps：可以认为网格的每个点都是很大的广场并且容纳所有的人，人可以走在有房子的点但是不进入房子。

分析：人-房子，很完美的带全都最小值匹配啊，人到一个房子的花费就是他们之间的曼哈顿距离，用这些距离构造一个二分图，然后用KM算法求出来最小费。下面是KM算法

***********************************************************************************************************************************

%d ", KM());
    }

    return 0;
}

View Code

研究了一下网络网络流里面的最小费用最大流，听着名字比较高大上吧，看了半天终于恍然大悟，其实还是最大流。但是为什么又叫最小费用呢？所谓的最小费用并不是从源点到汇点的最小费用，而是再保证最大流的前提下的最小费用，我们求最大流的的办法就是不断进行路径增广，而怎么增广路径就比较随意了，可以用深搜或者广搜，不管怎么样只要找到可以进行增广的路就行，如果在这个前提下我们找增广路的时候用最短路的办法去找，那么岂不是找的每条路都是花费最小的，而且最后无路时候就是最小花费了（同时也求出来了最大流），有了这个认识就可以写最消费最大流了。

%d ", MinCost());
    }

    return 0;
}