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。这样做的目的是为了使已被匹配的点的权值尽量小，从而使匹配的代价最小化。

相关问题

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); } }

这段代码是匈牙利算法中的子图相交增广函数的一部分。在这段代码中，首先初始化了一些变量和数据结构，包括 VisitedX 和 VisitedY 两个集合，它们分别表示已经访问过的 X 点和 Y 点。接着，将起点 start 加入 VisitedX 集合中。然后遍历所有的 Y 点，如果这个点已经匹配过，即 Trace[j] 不等于 -1，那么将它的匹配点 matchY[j] 加入 VisitedX 集合中，并将这个点 j 加入 VisitedY 集合中。这样就得到了两个集合 VisitedX 和 VisitedY，它们的交集表示子图中已经访问过的点，即匈牙利算法中的增广路。

void Hungarian::Enter(vector<vector<double>>& DistMatrix, vector<int>& Assignment) { int i, j; m = DistMatrix.size(); n = DistMatrix[0].size(); k = m > n ? m : n;//tìm số đỉnh nhiều nhất trong 2 bên X và Y //gán tất cả các cạnh là giá trị maxC ( rất lớn) for (i = 0; i < k; i++) { for (j = 0; j < k; j++) { if (i >= m || j >= n) { c[i][j] = maxC; continue; } if (DistMatrix[i][j] == 0) c[i][j] = maxC; else c[i][j] = DistMatrix[i][j]; } } }

这段代码是匈牙利算法中的初始化部分，主要是将给定的二分图的边权矩阵转化成匈牙利算法需要的邻接矩阵格式。具体来说，它首先确定了二分图中节点数较大的那一侧的节点数k，然后将邻接矩阵的所有元素初始化为一个非常大的值maxC。接着，对于每个有边的节点对(i,j)，将邻接矩阵中对应的元素赋值为这条边的边权值。如果这条边的边权值为0，那么将邻接矩阵中对应的元素也赋值为maxC，表示这条边不存在。

需要注意的是，这段代码中的c是一个二维数组，表示邻接矩阵。其中，c[i][j]表示节点i和节点j之间的边权值。m和n分别表示二分图中左侧和右侧节点的个数。maxC是一个非常大的值，用于表示不存在的边或者没有匹配的节点对之间的距离。