二分图匹配实例代码及整理
为依兰等地区用户提供了全套网页设计制作服务，及依兰网站建设行业解决方案。主营业务为成都做网站、网站建设、依兰网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
1、匈牙利算法
HDU 1150
#include#include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i
2、KM算法
HDU 2255
看了很多资料都还不是很懂、、先贴别人的模板
#include#include #include #include #include using namespace std; #define N 310 int map[N][N]; bool visitx[N], visity[N]; int lx[N], ly[N]; int match[N]; int n; bool Hungary(int u) //匈牙利算法 { visitx[u] = true; for(int i = 0; i < n; ++i) { if(!visity[i] && lx[u] + ly[i] == map[u][i]) { visity[i] = true; if(match[i] == -1 || Hungary(match[i])) { match[i] = u; return true; } } } return false; } void KM_perfect_match() { int temp; memset(lx, 0, sizeof(lx)); //初始化顶标 memset(ly, 0, sizeof(ly)); //ly[i]为0 for(int i = 0; i < n; ++i) //lx[i]为权值最大的边 for(int j = 0; j < n; ++j) lx[i] = max(lx[i], map[i][j]); for(int i = 0; i < n; ++i) //对n个点匹配 { while(1) { memset(visitx, false, sizeof(visitx)); memset(visity, false, sizeof(visity)); if(Hungary(i)) //匹配成功 break; else //匹配失败，找最小值 { temp = INT_MAX; for(int j = 0; j < n; ++j) //x在交错树中 if(visitx[j]) for(int k = 0; k < n; ++k) //y在交错树外 if(!visity[k] && temp > lx[j] + ly[k] - map[j][k]) temp = lx[j] + ly[k] - map[j][k]; for(int j = 0; j < n; ++j) //更新顶标 { if(visitx[j]) lx[j] -= temp; if(visity[j]) ly[j] += temp; } } } } } int main() { int ans; while(scanf("%d", &n) != EOF) { ans = 0; memset(match, -1, sizeof(match)); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", &map[i][j]); KM_perfect_match(); for(int i = 0; i < n; ++i) //权值相加 ans += map[match[i]][i]; printf("%d\n", ans); } return 0; }
3、多重匹配
HDU 3605 Escape
#include#include #include using namespace std; int n,m; int num[15]; int mpt[100005][15]; int vis[15]; int use[15]; int dp[15][100005]; int hungary(int x) { for(int i=1;i<=m;i++) { if(vis[i]==0&&mpt[x][i]==1) { vis[i]=1; if(use[i]
以上就是二分图匹配的实现代码，如有疑问请留言，或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！