如何编写并整理二分图匹配的实例代码？

本文共计1333个文字，预计阅读时间需要6分钟。

二分图匹配实例代码及整体理解

二分图匹配问题在图论中是一个经典问题，主要应用于解决配对问题，如医院与病人的配对、课程与学生的选课配对等。下面将提供一个简单的二分图匹配实例代码，并对整体进行简要理解。

代码示例

pythondef dfs(u, match, visited): for v in range(n): if graph[u][v] and not visited[v]: visited[v]=True if match[v]==-1 or dfs(match[v], match, visited): match[v]=u return True return False

def max_match(): match=[-1] * n for u in range(n): visited=[False] * n if dfs(u, match, visited): return True return False

假设n是顶点数，graph是一个n*n的矩阵，表示边的存在n=4graph=[ [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0]]

if max_match(): print(存在最大匹配)else: print(不存在最大匹配)

整体理解

1. 二分图定义：二分图是指顶点可以分成两个不相交的集合，使得每一条边都连接这两个集合中的顶点。

2. 匹配定义：匹配是指图中的一种边选择，使得没有两条边共享一个公共顶点。

3. 最大匹配：最大匹配是指图中边的最大数量，使得没有两条边共享一个公共顶点。

4. DFS算法：上述代码中使用的DFS（深度优先搜索）算法用于寻找增广路径。增广路径是指从未匹配的顶点出发，通过边连接到另一个未匹配的顶点的路径。

5. 匹配过程：通过不断寻找增广路径，并更新匹配关系，直到无法再找到增广路径为止，此时得到的匹配即为最大匹配。

通过上述代码和解释，我们可以理解二分图匹配的基本概念和解决方法。

二分图匹配实例代码及整理

1、匈牙利算法

HDU 1150

#include<stdio.h> #include<string.h> #include<algorithm> 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<m;i++) { if(vis[i]==0&&mpt[x][i]==1) { vis[i]=1; if(use[i]==-1||hungary(use[i])) { use[i]=x; return 1; } } } return 0; } int main() { while(scanf("%d",&n)!=EOF,n) { scanf("%d%d",&m,&k); int a,b,c; memset(mpt,0,sizeof(mpt)); for(int i=1;i<=k;i++) { scanf("%d%d%d",&c,&a,&b); mpt[a][b]=1; } int ans=0; memset(use,-1,sizeof(use)); for(int i=1;i<n;i++) { if(hungary(i)) { ans++; } memset(vis,0,sizeof(vis)); } printf("%d\n",ans); } return 0; }

2、KM算法

HDU 2255

看了很多资料都还不是很懂、、先贴别人的模板

#include<iostream> #include<cstdio> #include<cstring> #include<climits> #include<algorithm> 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<stdio.h> #include<string.h> #include<algorithm> 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]<num[i])//满足条件 { dp[i][use[i]++]=x; return 1; } //不满足则寻找增广路 for(int j=0;j<use[i];j++)//看能否回溯一个出去 { if(hungary(dp[i][j])) { dp[i][j]=x; return 1; } } } } return 0; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&mpt[i][j]); } } for(int i=1;i<=m;i++) scanf("%d",&num[i]); int ans=0; memset(use,0,sizeof(use)); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(!hungary(i)) { ans=1; break; } } if(ans==0) { printf("YES\n"); } else printf("NO\n"); } return 0; }

以上就是二分图匹配的实现代码，如有疑问请留言，或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！