algorithm - 带约束的二分匹配

标签 algorithm data-structures graph computer-science depth-first-search

我试图在两组顶点之间进行匹配,一组代表两支球队之间的相遇,另一组代表相遇可能发生的时间段。邻接图表示两个团队在任何给定时间段会面的可用性。这将是二分匹配。问题是我想限制这一点,这样任何团队都不会被分配到连续的时间段,更具体地说是连续两天的时间段。

因此,我已经尝试在向匹配添加边之前添加一个检查,在增广路径的末尾,检查前一天和第二天的时间段,如果它们已经匹配到任何比赛中的球队即将比赛。我用 Hopcroft-Karp 和 DFS 试过了。它没有用。

这不是二分匹配了吗?

任何帮助将不胜感激。

编辑:

正如下面的答案所建议的,我正在尝试将其实现为整数线性程序。以下代码很大程度上基于示例 from Google OR-tools on assignment matching 事实上,它似乎可以正确匹配,但没有我指定的约束。

// [START program]
// [START import]
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
// [END import]

/** MIP example that solves an assignment problem. */
public class GameMatching {
    static {
        System.loadLibrary("jniortools");
    }

    public static void main(String[] args) {
        // Data
        // [START data_model]
        // Adjacency matrix represents which games can happen on which dates
        int[][] adj = {
          {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
          {1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
          {0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
          {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
          {0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        };

        int numGames = adj.length;
        int numDates = adj[0].length;

        //represents which game time slots are on a given day (4 games on sundays, 2 on weekdays)
        int[][] days = {
              {0, 1, 2, 3},
              {4, 5},
              {6, 7},
              {8, 9, 10, 11},
              {12, 13},
              {14, 15},
              {16, 17},
              {18, 19},
              {20, 21, 22, 23},
              {24, 25},
              {26, 27},
              {28, 29},
              {30, 31},
              {32, 33, 34, 35},
              {36, 37},
              {38, 39},
              {40, 41},
              {42, 43},
              {44, 45, 46, 47},
              {48, 49},
              {50, 51},
              {52, 53, 54, 55},
              {56, 57},
              {58, 59},
              {60, 61},
              {62, 63},
              {64, 65, 66, 67},
              {68, 69},
              {70, 71},
              {72, 73},
              {74, 75},
              {76, 77, 78, 79}
        };
        //represents what day of the week is a day, a team can play thursday and sunday, but not sunday and monday 0 is sunday, 1 is monday...
        int[] weekDays = {0, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0};

        // teamToGames[i][j] represents a team i's, games j
        int[][] teamToGames = {
              {1, 3, 9, 16, 18, 26},
              {0, 8, 12, 16, 23, 28},
              {1, 5, 7, 13, 21, 27},
              {2, 5, 14, 17, 22, 26},
              {7, 15, 19, 21, 24, 28},
              {3, 10, 14, 20, 27, 29},
              {2, 6, 9, 13, 23, 29},
              {6, 8, 11, 18, 19, 25},
              {8, 4, 10, 11, 17, 24},
              {4, 12, 15, 20, 22, 25},
        };
       
        // [END data_model]

        // Solver
        // [START solver]
        // Create the linear solver with the CBC backend.
        MPSolver solver = new MPSolver("AssignmentMip", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);
        // [END solver]

        // Variables
        // [START variables]
        // x[i][j] is an array of 0-1 variables, which will be 1
        // if a game i is assigned to date j.
        MPVariable[][] match = new MPVariable[numGames][numDates];
        for (int i = 0; i < numGames; ++i) {
            for (int j = 0; j < numDates; ++j) {
                match[i][j] = solver.makeIntVar(0, 1, "");
            }
        }

        // [END variables]

        // Constraints
        // [START constraints]
        // Each game is assigned to at most one date.
        for (int i = 0; i < numGames; ++i) {
            MPConstraint constraint = solver.makeConstraint(0, 1, "");
            for (int j = 0; j < numDates; ++j) {
                constraint.setCoefficient(match[i][j], 1);
            }
        }
        // Each date is assigned to at most one game.
        for (int j = 0; j < numDates; ++j) {
            MPConstraint constraint = solver.makeConstraint(0, 1, "");
            for (int i = 0; i < numGames; ++i) {
                constraint.setCoefficient(match[i][j], 1);
            }
        }
        // Can only assign respecting adj matrix
        for (int i = 0; i < numGames; ++i) {
            for (int j = 0; j < numDates; ++j) {
                MPConstraint constraint = solver.makeConstraint(0, adj[i][j], "");
                constraint.setCoefficient(match[i][j], 1);
            }
        }

        // Cannot assign team to consecutive dates
        for (int i = 0; i < teamToGames.length; ++i) {
            for (int j = 0; j < days.length - 1; ++j) {
                if (weekDays[j] != 4) {
                    MPConstraint constraint = solver.makeConstraint(0, 1, "");
                    for (int k = 0; k < teamToGames[i].length; ++k) {
                        for (int l = 0; l < days[j].length; ++l) {
                            constraint.setCoefficient(match[teamToGames[i][k]][l], 1);
                        }
                        for (int l = 0; l < days[j+1].length; ++l) {
                            constraint.setCoefficient(match[teamToGames[i][k]][l], 1);
                        }
                    }
                }
            }
        }

        // [END constraints]

        // Objective
        // [START objective]
        MPObjective objective = solver.objective();
        for (int i = 0; i < numGames; ++i) {
            for (int j = 0; j < numDates; ++j) {
                objective.setCoefficient(match[i][j], 1);
            }
        }

        objective.setMaximization();
        // [END objective]

        // Solve
        // [START solve]
        MPSolver.ResultStatus resultStatus = solver.solve();
        // [END solve]

        // Print solution.
        // [START print_solution]
        // Check that the problem has a feasible solution.
        if (resultStatus == MPSolver.ResultStatus.OPTIMAL || resultStatus == MPSolver.ResultStatus.FEASIBLE) {
            System.out.println("Total matches: " + objective.value() + "\n");
            for (int i = 0; i < numGames; ++i) {
                for (int j = 0; j < numDates; ++j) {
                    // Test if x[i][j] is 0 or 1 (with tolerance for floating point
                    // arithmetic).
                    if (match[i][j].solutionValue() > 0.5) {
                        System.out.println("Game " + i + " assigned to date " + j);
                    }
                }
            }
        } else {
            System.err.println("No solution found.");
        }
        // [END print_solution]
    }

    // private GameMatching() {
    // }
}
// [END program]

编辑 这是显然有效的代码。我需要做最后一件事。最好在同一天进行两场比赛(如果其他限制条件允许),而不是在两个不同的日子里每天进行一场比赛。我的第一个想法是找到一种方法将每天的游戏限制为 0 或 2(或周日更多),但这并不总是可行的。因此,我们将不胜感激任何有关我如何做到这一点的帮助。

提前谢谢你。

最佳答案

我们可以有一个整数线性程序,其中团队要满足的每个约束都包含两个额外的 before 变量。例如,A 队在第 4 天会面:

{
  A_meets_on_4: 1,
  A_meets_before_4: 1,
  A_meets_before_5: 1
}

如果我们尝试将 A 分配给 3,我们会得到:

{
  A_meets_on_3: 1,
  A_meets_before_3: 1,
  A_meets_before_4: 1
}

如果我们尝试将 A 分配给 5,我们会得到:

{
  A_meets_on_5: 1,
  A_meets_before_5: 1,
  A_meets_before_6: 1
}

现在如果我们尝试分配,比如 3 和 4,我们得到:

{
  A_meets_on_3: 1,
  A_meets_on_4: 1,
  A_meets_before_3: 1,
  A_meets_before_4: 2
  A_meets_before_5: 1
}

但是,如果我们将所有 before 变量(如 A_meets_before_4)限制为小于 2,则不允许这样做。

如果我们尝试将 A 分配给 3 和 5,我们将得到:

{
  A_meets_on_3: 1,
  A_meets_on_5: 1,
  A_meets_before_3: 1,
  A_meets_before_4: 1
  A_meets_before_5: 1
  A_meets_before_6: 1
}

这是允许的。

关于algorithm - 带约束的二分匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62551855/

相关文章:

algorithm - 在图中找到 X 成本最低的树

java - 对不同 Java 集合进行基准测试的最佳实践是什么?

java - 使用 Java 树模型

python - 使用 PyDot 排列点图的头部?

graph - SAS 条形图测量不同变量的百分比(一个变量在 y 轴上测量,另一个通过条内的阴影显示)

c++ - 自定义排序的工作方式出乎意料

algorithm - 发现字符串中的连续重复模式

algorithm - 对一组特征向量进行采样以获得每个特征的 "uniform"直方图

c - 给定集合的幂集

python - 从头到尾循环