指派问题与匈牙利解法
指派问题概述：
实际中，会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的1项，每个人完成任务的时间不一样。于是就有一个问题，如何分配任务使得花费时间最少。
通俗来讲，就是n*n矩阵中，选取n个元素，每行每列各有1个元素，使得和最小。
如下图：
指派问题性质：
指派问题的最优解有这样一个性质，若从矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到归约矩阵，其最优解和原矩阵的最优解相同．
匈牙利法：
|
12 |
7 |
9 |
7 |
9 |
|
8 |
9 |
6 |
6 |
6 |
|
7 |
17 |
12 |
14 |
9 |
|
15 |
14 |
6 |
6 |
10 |
|
4 |
10 |
7 |
10 |
9 |
1.行归约：
每行元素减去该行的最小元素
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
2.列归约：
每列元素减去该列的最小元素
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
3.试指派：
(1)找到未被画线的含0元素最少的行列（行和列同时比较，行列的意思是某一行或某一列，下同）。
(2)找到该行列中未被画线的0元素，这就是一个独立0元素。对该0元素所在行和列画线。
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
(3)暂时不看被线覆盖的元素，重复(1)(2)直到没有线可以画。
(4)根据(2)找到的0元素个数判断，找到n个独立0元素则Success，小于n个则Fail.
4.画盖0线：
目标：做最少的直线数覆盖所有0元素，直线数就是独立0元素的个数。
注意：这跟3的线不同；不能用贪心法去画线，比如
1 0 0
1 1 0
1 0 1
若先画横的，则得画3条线，实际只需2条；若先画竖的，将矩阵转置后同理。
步骤3得出的独立0元素的位置
|
5 |
0 |
2 |
0 |
2 |
|
2 |
3 |
0 |
0 |
0 |
|
0 |
10 |
5 |
7 |
2 |
|
9 |
8 |
0 |
0 |
4 |
|
0 |
6 |
3 |
6 |
5 |
(1)对没有独立0元素的行打勾、
(2)对打勾的行所含0元素的列打勾
(3)对所有打勾的列中所含独立0元素的行打勾
(4)重复(2)(3)直到没有不能再打勾
(5)对打勾的列和没有打勾的行画画线，这就是最小盖0线。
|
5 |
0 |
2 |
0 |
2 |
|
|
2 |
3 |
0 |
0 |
0 |
|
|
0 |
10 |
5 |
7 |
2 |
√ |
|
9 |
8 |
0 |
0 |
4 |
|
|
0 |
6 |
3 |
6 |
5 |
√ |
|
√ |
|
5 |
0 |
2 |
0 |
2 |
|
|
2 |
3 |
0 |
0 |
0 |
|
|
0 |
10 |
5 |
7 |
2 |
√ |
|
9 |
8 |
0 |
0 |
4 |
|
|
0 |
6 |
3 |
6 |
5 |
√ |
|
√ |
5.更新矩阵：
(1)对没有被线划到的数中，找到最小的数。
(2)对没有被线划到的数中，减去最小的数。
(3)对被2条线划到的数中，加上最小的数。
|
7 |
0 |
2 |
0 |
2 |
|
4 |
3 |
0 |
0 |
0 |
|
0 |
8 |
3 |
5 |
0 |
|
11 |
8 |
0 |
0 |
4 |
|
0 |
4 |
1 |
4 |
3 |
6.重复3-5直到成功。
|
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
0 |
0 |
sum = 7+6+9+6+4 = 32
练习：http://soj.me/show_problem.php?pid=1002&cid=1085
注意题目是求最大值，所以需要对矩阵做一点处理。