首页 > 代码库 > Maximum Cardinality Bipartite Matching: Augmenting Path Algorithm
Maximum Cardinality Bipartite Matching: Augmenting Path Algorithm
http://www.csie.ntnu.edu.tw/~u91029/Matching.html
1 int nx,ny; 2 int mx[N],my[N]; 3 bool vy[N]; 4 bool g[N][N]; 5 6 int decode(int x,int y) {return x*15+y;} 7 8 bool dfs(int x) 9 {10 for(int y=0;y<ny;++y)11 if(g[x][y] && !vy[y])12 {13 vy[y]=1;14 if(my[y]==-1 || dfs(my[y]))15 {16 mx[x]=y;17 my[y]=x;18 return 1;19 }20 }21 return 0;22 }23 24 int b_matching()25 {26 memset(mx,-1,sizeof(mx));27 memset(my,-1,sizeof(my));28 int c=0;29 for(int x=0;x<nx;++x)30 {31 memset(vy,0,sizeof(vy));32 if(dfs(x)) ++c;33 }34 return c;35 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。