首页 > 代码库 > 二分图最大匹配
二分图最大匹配
在图论中，匹配是指两两没有公共点的边集。
二分图的最大匹配是这样的：给出一个二分图，找到一个边数最大的匹配，即选尽量多的边，使得任意两条选中的边没有公共点。
如果所有的点都是匹配点（匹配中的某一条边的端点），则称这个匹配是完美匹配（perfect matching）。
下面我们考虑二分图都是联通图，如果是非联通图，孤立点我们也不处理，所以相当于联通图。
增广路定理：
我们用未盖点表示不与任何匹配边相邻的顶点，其它点为匹配点，即恰好和一条匹配边邻接的点。
从未盖点出发，依次经过非匹配边、匹配边、非匹配边、匹配边....，所得到的路径为交替路，如果交替路的终点是一个未盖点，则称这条交替路为一条增广路
在增广路中，非匹配边比匹配边多一条。
如图 
那么可以将非匹配边变成匹配边，匹配边变成非匹配边，那么匹配的边数就+1
一个匹配是最大匹配的充分必要条件是找不到增广路。
所以，得到一个算法，每次选一个未盖点u进行dfs，如果找不到u开头的增光路，则换一个未盖点进行dfs，且以后再也不从u出发找增广路
即如果以后存在一个从u出发的增广路，那么现在就找得到（具体证明，我也不知道）。
hdu 2063、
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 1111; 4 int Map[N][N]; 5 int cx[N]; 6 int cy[N]; 7 bool vis[N]; 8 int k,m,n; 9 10 bool dfs(int u)//从未盖点u出发，寻找增广路11 {12 int i;13 for(i=1; i<=m; ++i)14 {15 if(Map[u][i] && !vis[i])16 {17 vis[i] = true;18 if(cy[i] == -1 || dfs(cy[i]))//如果能找到增广路19 {20 cy[i] = u;//匹配标记， i 和u配对21 cx[u] = i;22 return true;23 }24 }25 }26 return false;27 }28 int MaxMatch()29 {30 memset(cy, -1, sizeof(cy));31 memset(cx, -1, sizeof(cx));32 int i, ans = 0;33 for(i=1; i<=n; ++i)34 {35 if(cx[i] == -1)//每次从未盖点出发，寻找增广路36 {37 memset(vis,0,sizeof(vis));38 ans += dfs(i);//如果找到增广路，则匹配边的个数+139 }40 }41 return ans;42 }43 int main()44 {45 46 int a,b,i;47 while(scanf("%d%d%d",&k,&n,&m)==3 && k)48 {49 memset(Map, 0, sizeof(Map));50 for(i=0; i<k; ++i)51 {52 scanf("%d%d",&a,&b);53 Map[a][b] = 1;54 }55 int ans = MaxMatch();56 printf("%d\n",ans);57 58 }59 return 0;60 }
二分图最大匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。