两个算法题

medie2005

1、
自动打开一个文本文件，读取文本文件中的表格（N列*N行），格式自定
有N个机器及N个任务，大概如下
JOB Job 1 Job 2 Job 3 Job 4
Machine 1 14 5 8 7
Machine 2 2 12 6 5
Machine 3 7 8 3 9
Machine 4 2 4 6 10
每个机器完成不同的任务所需的时间是不同的，且机器只能被分配一个任务，不需要考虑重新利用问题，求最短的分配方案

2、
自动打开一个文本文件，读取文本文件中的表格（N列*N行），格式自定
里面的表格代表的是有 N个村庄，表格列出了每个村庄到其他村庄的距离
From Village 1 Village 2 Village 3 Village 4 Village 5 Village 6
Village 1 0 10 20 30 30 20
Village 2 10 0 25 35 20 10
Village 3 20 25 0 15 30 20
Village 4 30 35 15 0 15 25
Village 5 30 20 30 15 0 14
Village 6 20 10 20 25 14 0
现在想造消防站，求最少需要造几个消防站，这样可以让任意村庄都至少有一个消防站可以在15分钟内到达

litaoye

medie2005也看到这两个问题了么？好奇怪，最近讨论规划问题的特别多。

第一题匈牙利算法，复杂度大概n^3
第二题应该还是最小顶点覆盖的问题

mathe

第一题应该是指派问题，我记得是运筹学里面的。