用匈牙利算法解決相親類型問題的數(shù)學模型-資料下載頁
2025-04-07 02:54本頁面
【正文】 60。 lx[i] = INF。 ly[i] = 0。 for(j = 0。 j n。 j++) { lx[i] = max(lx[i], edge[i][j])。 } } bool perfect = false。 while(!perfect) { // 初始化鄰接矩陣 for(i = 0。 i n。 i++) { for(j = 0。 j n。 j++) { if(lx[i]+ly[j] == edge[i][j]) map[i][j] = true。 else map[i][j] = false。 } } // 匹配過程 int live = 0。 memset(match, 1, sizeof(match))。 for(i = 0。 i n。 i++) { memset(xckd, false, sizeof(xckd))。 memset(yckd, false, sizeof(yckd))。 if(DFS(i, n)) live++。 else { xckd[i] = true。 break。 } } if(live == n) perfect = true。 else { // 修改標號過程 int ex = INF。 for(i = 0。 i n。 i++) { for(j = 0。 xckd[i] amp。amp。 j n。 j++) { if(!yckd[j]) ex = min(ex, lx[i]+ly[j]edge[i][j])。 } } for(i = 0。 i n。 i++) { if(xckd[i]) lx[i] = ex。 if(yckd[i]) ly[i] += ex。 } } } } // 此函數(shù)用來尋找是否有以Xp為起點的增廣路徑，返回值為是否含有增廣路 bool DFS(int p, const int n) { int i。 for(i = 0。 i n。 i++) { if(!yckd[i] amp。amp。 map[p][i]) { yckd[i] = true。 int t = match[i]。 match[i] = p。 if(t == 1 || DFS(t, n)) { return true。 } match[i] = t。 if(t != 1) xckd[t] = true。 } } return false。 } int main() { int n, edge[size][size]。 // edge[i][j]為連接Xi與Yj的邊的權(quán)值 int i。 /*************************************************** * 在此處要做的工作 : * 讀取二分圖每兩點間邊的權(quán)并保存在edge[][]中, * 若X與Y數(shù)目不等，應(yīng)添加配合的頂點 * 保存二分圖中X與Y的頂點數(shù)n,若上一步不等應(yīng)保 * 存添加頂點完畢后的n ***************************************************/ KM_Perfect_Match(n, edge)。 int cost = 0。 for(i = 0。 i n。 i++) { cost += edge[match[i]][i]。 } // cost 為最大匹配的總和, match[]中保存匹配信息 return 0。 }17
數(shù)學相關(guān)推薦
鄂ICP備17016276號-1