与异常值匹配的最小成本
Min cost matching with outliers
给定一个完整的二分图 G = (V1, V2; E), |V1|=|V2|=n 和每条边的非负成本最小成本二分匹配问题找到 G 的一个分区到n对由边连接的顶点，使得边成本的总和最小化。
这个问题可以使用 min cost flow 算法解决，方法是添加一个源和汇点连接到每个组，权重为 0，容量为 1。
但是如果我们得到一个数字 m < n 作为输入并且想要找到 m 对的分区以使总成本最小化怎么办？
起初我以为我们可以在开头添加另一个顶点连接到原始源，权重为0，容量为m，并将其称为新源，这样最大流量将是m，它应该选择只有 m 对。
然而，当我 运行 这个算法多次使用 boost 的最小成本流函数时，出现了 2 个大问题：
1) 边中的流量并不总是整数（例如，流量不是 0 或 1，而是 0.5）。
2) 有许多可能的（非整数）解决方案，因此即使对于具有不同顺序的相同输入，算法也会输出不同的结果。
当我将m设置为n时，这两个问题都解决了。
所以我的问题是：有没有办法解决这个问题，如果没有，是否有另一种算法可以解决最小成本二分匹配与异常值问题？
我刚刚发现了我在问题中描述的算法，并说它不起作用实际上确实起作用了，这是因为当我将所有成本乘以 10000 时内部提升最小成本流函数引起的浮点错误所有问题都解决了。
给定一个完整的二分图 G = (V1, V2; E), |V1|=|V2|=n 和每条边的非负成本最小成本二分匹配问题找到 G 的一个分区到n对由边连接的顶点，使得边成本的总和最小化。
这个问题可以使用 min cost flow 算法解决，方法是添加一个源和汇点连接到每个组，权重为 0，容量为 1。
但是如果我们得到一个数字 m < n 作为输入并且想要找到 m 对的分区以使总成本最小化怎么办？
起初我以为我们可以在开头添加另一个顶点连接到原始源，权重为0，容量为m，并将其称为新源，这样最大流量将是m，它应该选择只有 m 对。
然而，当我 运行 这个算法多次使用 boost 的最小成本流函数时，出现了 2 个大问题：
1) 边中的流量并不总是整数（例如，流量不是 0 或 1，而是 0.5）。
2) 有许多可能的（非整数）解决方案，因此即使对于具有不同顺序的相同输入，算法也会输出不同的结果。
当我将m设置为n时，这两个问题都解决了。
所以我的问题是：有没有办法解决这个问题，如果没有，是否有另一种算法可以解决最小成本二分匹配与异常值问题？
我刚刚发现了我在问题中描述的算法，并说它不起作用实际上确实起作用了，这是因为当我将所有成本乘以 10000 时内部提升最小成本流函数引起的浮点错误所有问题都解决了。