double Hungarian::GetC(int i, int j) { return c[i][j] - Fx[i] - Fy[j]; }

这段代码是匈牙利算法中计算两点间费用的函数。在匈牙利算法中，需要寻找二分图中的最大权匹配，其中每个点都有一个权重（或费用），而 GetC(i,j) 函数就是用来计算第 i 个点和第 j 个点之间的费用。其中，c[i][j] 表示第 i 个点和第 j 个点之间的原始费用（即没有经过任何调整的费用），而 Fx[i] 和 Fy[j] 分别表示第 i 个点和第 j 个点的横向和纵向调整值。通过对原始费用和横向、纵向调整值进行加减操作，就可以得到两点间的实际费用。

相关问题

void Hungarian::Init() { int i, j; //Khởi tạo ban đầu 2 bộ ghép đều rỗng (các giá trị được gán bằng -1 nghĩa là chưa có // đỉnh X gán với Y hoặc ngược lại) for (i = 0; i < MAX; i++) { matchX[i] = -1; matchY[i] = -1; } //tìm trọng số nhỏ nhất của các cạnh liên thuộc với X[i] for (i = 0; i < k; i++) { Fx[i] = maxC; for (j = 0; j < k; j++) { if (c[i][j] < Fx[i]) { Fx[i] = c[i][j]; } } } //tìm trọng số nhỏ nhất của các cạnh liên thuộc với Y[j] for (j = 0; j < k; j++) { Fy[j] = maxC; for (i = 0; i < k; i++) { if (c[i][j] - Fx[i] < Fy[j]) { Fy[j] = c[i][j] - Fx[i]; } } } }

这段代码是匈牙利算法的初始化函数，主要实现以下几个任务：

1. 初始化匹配数组matchX和matchY，初始时没有顶点被匹配，所以数组中所有值都为-1。
2. 对于每个顶点X[i]，计算其与相邻顶点Y[j]之间边的最小权值，并将其保存在Fx[i]中。
3. 对于每个顶点Y[j]，计算与相邻顶点X[i]之间边的权值减去Fx[i]的最小值，并将其保存在Fy[j]中。

以上步骤是匈牙利算法的预处理步骤，在找增广路时会用到这些信息。其中，maxC是一个较大的常数，起到初始化Fx和Fy时的默认最大值的作用。

void Hungarian::SubX_AddY() { int i, j, t; double Delta; set<int> VisitedX, VisitedY; /* Để ý rằng: VisitedY = {y \ Trace[y] khác -1} VisitedX = {start} giao match(VisitedY) = {start} giao {matchY[y] Trace[y] khác -1} */ VisitedX.insert(start); for (j = 0; j < k; j++) { if (Trace[j] != -1) { VisitedX.insert(matchY[j]); VisitedY.insert(j); } }Delta = maxC; for (i = 0; i < k; i++) { if (VisitedX.find(i) != VisitedX.end()) { for (j = 0; j < k; j++) { if ((VisitedY.find(j) == VisitedY.end()) && (GetC(i, j) < Delta)) Delta = GetC(i, j); } } }for (t = 0; t < k; t++) { //trừ trọng số những cạnh liên thuộc với VisitedX đi Delta if (VisitedX.find(t) != VisitedX.end()) Fx[t] = Fx[t] + Delta; //Cộng trọng số những cạnh liên thuộc với VisitedY lên Delta if (VisitedY.find(t) != VisitedY.end()) Fy[t] = Fy[t] - Delta; } }

这段代码是匈牙利算法中的"SubX_AddY"步骤，用于更新节点权值。具体来说，它的作用是从未被匹配的点中找出与已被匹配的点相邻且边权最小的点，然后更新所有与这些点相邻的点的权值。这个过程会涉及到两个向量Fx和Fy，它们分别表示未被匹配的点和已被匹配的点的权值。在这个过程中，我们先将所有与已被匹配的点相邻的点加入VisitedX和VisitedY中，然后遍历VisitedX中的所有点，找到与之相邻且未被匹配的点中边权最小的点，记为Delta，然后更新所有与VisitedX和VisitedY相邻的点的权值。具体来说，对于VisitedX中的点，我们将它们的权值加上Delta，对于VisitedY中的点，我们将它们的权值减去Delta。这样做的目的是为了使已被匹配的点的权值尽量小，从而使匹配的代价最小化。