首页 > 代码库 > 最大匹配必须边
最大匹配必须边
poj1486
题意：
给出一些矩形的坐标和一些点的坐标，若点在矩形内，则该点和该矩形匹配。
问哪些匹配边是可以唯一确定的，可以先求出最大匹配，然后每次删除一条匹配边，
然后再求最大匹配，如果匹配个数不变，那么该边不是必须边，否则就是必须边
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 1000; 4 struct node 5 { 6 int xMin,xMax,yMin,yMax; 7 }slide[N]; 8 int Map[N][N]; 9 bool vis[N];10 int cy[N];11 int cx[N];12 int n;13 int path[N];14 bool dfs(int u)15 {16 for(int i=0; i<n; ++i)17 {18 if(!vis[i] && Map[u][i])19 {20 vis[i] = true;21 if(cy[i]==-1 || dfs(cy[i]))22 {23 cy[i] = u;24 cx[u] = i;25 return true;26 }27 }28 }29 return false;30 }31 int MaxMatch()32 {33 int cnt = 0;34 memset(cy, -1, sizeof(cy));35 memset(cx, -1, sizeof(cx));36 for(int i=0; i<n; ++i)37 {38 if(cx[i]==-1)39 {40 memset(vis, 0, sizeof(vis));41 cnt += dfs(i);42 }43 }44 return cnt;45 }46 int main()47 {48 49 int i,j,x,y;50 int tCase = 1;51 while(true)52 {53 scanf("%d",&n);54 if(n == 0)55 break;56 for(i=0; i<n; ++i) 57 scanf("%d%d%d%d",&slide[i].xMin,&slide[i].xMax,58 &slide[i].yMin,&slide[i].yMax);59 memset(Map, 0, sizeof(Map));60 for(i=0; i<n; ++i)61 {62 scanf("%d%d",&x,&y);63 for(j=0; j<n; ++j)64 {65 if(x>=slide[j].xMin && x<=slide[j].xMax 66 &&y>=slide[j].yMin && y<=slide[j].yMax)67 Map[j][i] = 1;68 }69 }70 printf("Heap %d\n",tCase++);71 int ans = MaxMatch();//求出最大匹配72 bool flag = false;73 for(i=0; i<n; ++i)//记录X集合中的i与Y集合中的那些点匹配74 path[i] = cx[i];75 76 for(i=0; i<n; ++i)77 {78 Map[i][path[i]] = 0;//删除匹配边79 if(ans == MaxMatch())80 continue;81 //如果，匹配的个数减少，那么该匹配边是必须边82 if(flag)83 printf(" ");84 flag = true;85 printf("(%c,%d)",‘A‘+i,path[i]+1);86 Map[i][path[i]] =1;87 }88 89 if(!flag)90 printf("none");91 puts("");92 puts("");93 94 }95 return 0;96 }
最大匹配必须边
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。