最优匹配题解.doc

最优匹配题解.doc 的条件与要求几乎都是一样的。 (M3) (N代表点 ) (N*E"2)到0(N'2*E) 。因此这次的代码里面我有部分的题 目用了两种做法，有些题目只用了 KM算法。
P0J2195【基础】
题目大意：
地图上有若干个人和若干间房子，现在要让所有人都走到房子里，每间房子只 能容纳一个人。 所有人进入房子所需要的最小花费。
输入：
有若干组测试数据。每一组测试数据的第一行有两个整数N和M・表示地图是N 行M列的。接下来给出一个NXM的矩阵，如果一个点是”则表示是空地.
“m”代表这一格有一个人，“H”代表这一格有一间房子。N二M=0时代表测试 数据结束。1CN、M<=100・最多有100个房子。
输出：
。
题解：
。 能比SPFA费用流跑得快得多了 (0ms： 125ms)。
P0J3565【基础】
题目大意，
有N只蚂蚁和N棵苹果树(lWNUlOO)・要为每一只蚂蚁分配一棵苹果树。蚂 路线之间不能有重复。现在请求岀一种可行的分配方式。
输入丫 第一行有一个整数N。接下来N行每一行有两个整数xi・yi・分别表示一个蚂
蚁窝的坐标（-lOOOOVxi・yi<=10000）・接下来N行每一行有两个整数表示一 棵苹果树的坐标。
输岀：
N行，第i行有一个整数Ai・表示第Ai棵苹果树分配给第i个蚂蚁。
题解：
这一题的做法和P0J2195 言（最坑爹的是不知道为什么读入坐标也要double・反正int读入是会挂 的……）・ 。
POJ3686【中等】
题目大意，
有N个订单和M个机器（1UN、M<=50）・己知第i个订单在第j个机器完成的 时间为Mij・ 订单后才能接着完成下一个订单。请求出N个订单完成时间的平均值最少为多 少。
输入：
。
接下来每一组测试数据的第一行是一个空行，与上一组测试数据分割。每个测 试数据的第二行有两个整数N和M。接下来是一个N行M列的矩阵，第i行第j 列表示Mi j的值。
输出：
。
题解:
这一题理解上有一些困难（我觉得是题目叙述的原因……）・所以重在建图。 应该说是那么多台机器，某一时刻只能开一台，然后其他等着。也就是说，假 设某个机器处理了 ，一种是真正