首页 > 代码库 > 二分图行列匹配与最大匹配必须边
二分图行列匹配与最大匹配必须边
hdu1287
题意:在棋盘上放置车,要求车不能相互攻击,即要求车要在不同的行和列,二分图行列匹配
但是又问,那些点如果不放置车,就不能形成最大匹配,即哪些边是最大匹配的必须边
判断是否是最大匹配的必须边,只要删除该边之后做匹配,将匹配的个数与原先的个数比较就知道该边是不是最大匹配的必须边
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 100 + 10; 4 int Map[N][N]; 5 int n,m,k; 6 bool vis[N]; 7 int cy[N],cx[N]; 8 9 bool dfs(int u)10 {11 for(int i=0; i<m; ++i)12 {13 if(!vis[i] && Map[u][i]==1)14 {15 vis[i] = true;16 if(cy[i]==-1 || dfs(cy[i]))17 {18 cy[i] = u;19 cx[u] = i;20 return true;21 }22 }23 }24 return false;25 }26 int MaxMatch()27 {28 memset(cx, -1, sizeof(cx));29 memset(cy, -1, sizeof(cy));30 int cnt = 0;31 for(int i=0; i<n; ++i)32 {33 if(cx[i] == -1)34 {35 memset(vis, 0, sizeof(vis));36 cnt += dfs(i);37 }38 }39 return cnt;40 }41 int main()42 {43 int i,j,x,y;44 int tCase = 1;45 while(scanf("%d%d%d",&n,&m,&k)!=EOF)46 {47 memset(Map, 0, sizeof(Map));48 for(i=0; i<k; ++i)49 {50 scanf("%d%d",&x,&y);51 x-=1;y-=1;52 Map[x][y] = 1;53 }54 int ans = MaxMatch();55 int ans2 = 0;56 for(i=0; i<n; ++i)57 for(j=0; j<m; ++j)58 if(Map[i][j] == 1)59 {60 Map[i][j] = 0;//删边61 int cnt = MaxMatch();62 if(cnt != ans)63 ans2++;64 Map[i][j] = 1;65 }66 printf("Board %d have %d important blanks for %d chessmen.\n",tCase++,ans2,ans);67 }68 return 0;69 }
二分图行列匹配与最大匹配必须边
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。