二分图最佳带权匹配
二分图最佳带權匹配问题是指在给定带权二分图上求出一个最大匹配的问题,使得所有匹配边权值之和最大。这个问题也被称为二分图最优匹配。[1]
定义编辑
一个带权二分图 中的边 都带有一个权值 。该二分图的一个最佳带权匹配是它所有匹配中,所有匹配边权值之和中最大的一个。
求解方法编辑
KM算法编辑
直接使用KM算法求解。
最小费用最大流编辑
通过建立模型,使用费用流算法解决。
参考程序编辑
C++编辑
#include <cstdio>#include <string.h>#include <vector>#include <algorithm>#include <climits>using namespace std;int const MAX = 1000;int const inf = INT_MAX;int w[MAX][MAX];int link[MAX];//代表当前与Y集合中配对的X集合中的点int visx[MAX], visy[MAX];int lx[MAX], ly[MAX];int n, m;//代表X和Y中元素的个数 int can(int t){ visx[t] = 1; for(int i = 1; i <= m; i++){ if(!visy[i] && lx[t] + ly[i] == w[t][i]){//这里“lx[t]+ly[i]==w[t][i]”决定了这是在相等子图中找增广路的前提,非常重要 visy[i] = 1; if(link[i] == -1 || can(link[i])){ link[i] = t; return 1; } } } return 0;}int km(void){ int sum = 0; memset(ly, 0, sizeof(ly)); for(int i = 1; i <= n; i++){//把各个lx的值都设为当前w[i][j]的最大值 lx[i] = -inf; for(int j = 1; j <= n; j++){ if(lx[i] < w[i][j]) lx[i] = w[i][j]; } } memset(link, -1, sizeof(link)); for(int i = 1; i <= n; i++){ while(1){ memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if(can(i))//如果它能够形成一条增广路径,那么就break break; int d = inf;//否则,后面应该加入新的边,这里应该先计算d值 for(int j = 1; j <= n; j++)//对于搜索过的路径上的XY点,设该路径上的X顶点集为S,Y顶点集为T,对所有在S中的点xi及不在T中的点yj if(visx[j]) for(int k = 1; k <= m; k++) if(!visy[k]) d = min(d, lx[j] + ly[k] - w[j][k]); if(d == inf) return -1;//找不到可以加入的边,返回失败(即找不到完美匹配) for (int j = 1; j <= n; j++) if (visx[j]) lx[j] -= d; for(int j = 1; j <= m; j++) if(visy[j]) ly[j] += d; } } for(int i = 1; i <= m; i++) if(link[i] > -1) sum += w[link[i]][i]; return sum;}
参考文献编辑
- ^ 李煜东. suan fa jing sai jing jie zhi nan. zhong yuan chu ban chuang mei ji tuan - he nan dian zi ying xiang chu ban she. ISBN 978-7-89388-198-5.
🔥 Top keywords: Baike: 首页Special:搜索毛泽东家族榮耀之繼承者天之驕女鐵拳英雄九龍城寨之圍城黃循財背着善宰跑篠崎泫妮妃雅新生 (网络剧)劉偉健斯洛伐克习近平劉俊謙 (香港)李显龙歌手2024佛誕淚之女王2024年泰國羽球公開賽新加坡總理邊佑錫新加坡Energy (組合)庆余年九龍寨城六四事件家族榮耀金智媛彌助菲律宾胖猫跳江事件劉寶傑DAY6林峯張文傑李光耀神耆小子張鳳妮黃世聰Seventeen (組合)维基百科願榮光歸香港中華民國鬼滅之刃 柱訓練篇2024年英雄联盟季中邀请赛中华人民共和国TripleS金秀賢 (男演員)罗伯特·菲佐井柏然2024年世界女排联赛黃偉哲怪獸8號佘詩曼Foodpanda金惠奫新加坡总统香緹·摩爾于北辰 (1968年)王嘉爾笑看風雲排球少年!!角色列表林飛帆郭葦昀馴鹿寶貝翁靜晶猩球崛起:王國誕生ILLIT尼古拉·約基奇春色寄情人周殷廷鬼滅之刃排球少年!!吳釗燮逆天奇案2不夠善良的我們BABYMONSTER李正皓尚达曼BOYNEXTDOOR胡子彤IVE (組合)陳靜 (香港)香港吴作栋黃道十二宮凡希亚·奥伊亚胡宇威長洲太平清醮張員瑛搜查班長1958伍允龍习明泽黄岩岛賴清德偶然遇見的你虽然不是英雄