问一个简单算法的思路（指派问题）

Question

有一个n×n矩阵，里面有若干个元素是0，要求在每一不同行不同列中，分别能找到一个0（每一行找一个0，每一列找一个0）。
如果这个要求作不到那就用最少的直线（行线或者列线）划去所有的0！

Answer 1

可能对原题理解不是很正确假设矩阵是这样的
1，0，0，5
2，0，6，8
0，4，9，7
7，6，3，0
这样的矩阵是符合第一个要求的。因为可以找到如下的几个0
1，0，X，5
2，X，6，8
X，4，9，7
7，6，3，X
这样的话我先找到所有为0的节点的坐标
（1，2）
（1，3）
（2，2）
（3，1）
（4，4）
我的理解是，只要这个坐标组成的二维数组中第一列和第二列里1，2，3，4这四个数字是全的，那么肯定符合第一个要求。如果不全，那就是说不能满足“在每一不同行不同列中，分别能找到一个0”
这时只需要看行和列里面哪个缺少的数字多，如果行里面缺少的数字多，那就用行线去划0
比如数组如下
（1，2）
（2，2）
（3，1）
这时候只有3个0，那么我用行线划0需要3条，但是用列线划0只需要两条这个例子是4X4的矩阵，n维的道理一样也不知道想的对不对，我觉得在线性代数里应该能够作出证明的，但是，呵呵，都还给老师了