首页 > 代码库 > hdu1507 最大匹配
hdu1507 最大匹配
题目大意：
在 n*m在矩阵中，有一些点被标记为黑色，问可以多少对相邻的没有重复的白色块。
思路：
看上去与二分匹配毫无关系。但是没有其他好的解法，转化为二分匹配是正解。二分匹配的条件是{X,Y|E}, X（Y）集合内的元素没有关系。这题可以把i+j为奇数归为X，偶数则归为Y。从头开始扫描，只要某点不是黑色的，那么可以试着向上下左右建边，不过也需要四个方向的点不是黑色才可以。由于n ,m <=100，所有点数有10000，所有用邻接矩阵存图会超内存。用邻接表存图就好了。邻接表的存图方式是建立一个动态数组，如果有边u->v,则将v存入u的数组。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<vector> 6 #include<algorithm> 7 using namespace std; 8 const int N=10150,INF=0x3f3f3f3f; 9 int cx[N],cy[N],dx[N],dy[N],vis[102][102]; 10 bool bmask[N]; 11 int nx,ny,dis,ans; 12 vector<int> bmap[N]; 13 bool searchpath() 14 { 15 queue<int> q; 16 dis=INF; 17 memset(dx,-1,sizeof(dx)); 18 memset(dy,-1,sizeof(dy)); 19 for(int i=1;i<=nx;i++) 20 { 21 if(cx[i]==-1){ q.push(i); dx[i]=0; } 22 while(!q.empty()) 23 { 24 int u=q.front(); q.pop(); 25 if(dx[u]>dis) break; 26 for(int i=0;i<bmap[u].size();i++) 27 { 28 int v=bmap[u][i]; 29 if(dy[v]==-1) 30 { 31 dy[v]= dx[u] + 1; 32 if(cy[v]==-1) dis=dy[v]; 33 else 34 { 35 dx[cy[v]]= dy[v]+1; 36 q.push(cy[v]); 37 } 38 } 39 } 40 } 41 } 42 return dis!=INF; 43 } 44 int findpath(int u) 45 { 46 for(int i=0;i<bmap[u].size();i++) 47 { 48 int v=bmap[u][i]; 49 if(!bmask[v]&&dy[v]==dx[u]+1) 50 { 51 bmask[v]=1; 52 if(cy[v]!=-1&&dy[v]==dis) continue; 53 if(cy[v]==-1||findpath(cy[v])) 54 { 55 cy[v]=u; cx[u]=v; 56 return 1; 57 } 58 } 59 } 60 return 0; 61 } 62 void maxmatch() 63 { 64 ans=0; 65 memset(cx,-1,sizeof(cx)); 66 memset(cy,-1,sizeof(cy)); 67 while(searchpath()) 68 { 69 memset(bmask,0,sizeof(bmask)); 70 for(int i=1;i<=nx;i++) 71 if(cx[i]==-1) ans+=findpath(i); 72 } 73 } 74 void init() 75 { 76 for(int i=0;i<N;i++) bmap[i].clear(); 77 memset(vis,0,sizeof(vis)); 78 } 79 int main() 80 { 81 //freopen("test.txt","r",stdin); 82 int n,m,t,i,j,k,a,b; 83 while(scanf("%d%d",&n,&m)!=EOF) 84 { 85 if(!n) break; 86 init(); 87 scanf("%d",&t); 88 while(t--) 89 { 90 scanf("%d%d",&i,&j); 91 vis[i][j]=1; 92 } 93 for(i=1;i<=n;i++) 94 { 95 for(j=1;j<=m;j++) 96 { 97 if(!vis[i][j]&&((i+j)%2)) 98 { 99 a=(i-1)*m + j;100 if(!vis[i][j-1]&&j>1) //左101 {102 b=a-1;103 bmap[a].push_back(b);104 }105 if(!vis[i][j+1]&&j<m) //右106 {107 b=a+1;108 bmap[a].push_back(b);109 }110 if(!vis[i-1][j]&&i>1) //上111 {112 b=a-m;113 bmap[a].push_back(b);114 }115 if(!vis[i+1][j]&&i<n) //下116 {117 b=a+m;118 bmap[a].push_back(b);119 }120 }121 }122 }123 nx=ny=n*m;124 maxmatch();125 printf("%d\n",ans);126 for(i=1;i<=n*m;i++)127 {128 if(cx[i]==-1) continue;129 a=i/m; b=i%m;130 if(!b) b=m; else a++;131 printf("(%d,%d)--",a,b);132 a=cx[i]/m; b=cx[i]%m;133 if(!b) b=m; else a++;134 printf("(%d,%d)\n",a,b);135 }136 }137 return 0;138 }
hdu1507 最大匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。