首页 > 代码库 > hdu Uncle Tom's Inherited Land*(1*2矩阵覆盖,最大匹配)
hdu Uncle Tom's Inherited Land*(1*2矩阵覆盖,最大匹配)
http://acm.hdu.edu.cn/showproblem.php?pid=1507
大致题意:在一个n*m的格子上,黑色的地方不可用,问在白色格子上最多可放多少1*2的矩阵。
思路:建图,每个白色格子与它临近的上下左右的白色格子建边,求最大匹配,答案为最大匹配/2,因为是双向图。最后输出匹配边时,当找到一组匹配边记得将该边标记,以防重复计算。
#include <stdio.h> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <queue> #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1000000007; const int maxn = 110; int n,m,k; vector <int> edge[maxn]; int Map[maxn][maxn]; int match[10010],chk[10010]; int cnt; int addre[10010]; void debug() { for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) printf("%d%d ",Map[i][j],addre[Map[i][j]]); printf("\n"); } } int dfs(int p) { for(int i = 0; i < (int)edge[p].size(); i++) { int q = edge[p][i]; if(!chk[q]) { chk[q] = 1; if(match[q] == -1 || dfs(match[q])) { match[q] = p; return 1; } } } return 0; } void output() { int vis[10010]; int x,y,xx,yy,tmp; memset(vis,0,sizeof(vis)); for(int i = 1; i <= cnt; i++) { if(match[i] != -1 && !vis[i]) { tmp = match[i]; if(!vis[tmp] && i != tmp) { vis[i] = 1; vis[tmp] = 1; xx = addre[tmp]/m+1; yy = addre[tmp]%m+1; x = addre[i]/m+1; y = addre[i]%m+1; printf("(%d,%d)--(%d,%d)\n",x,y,xx,yy); } } } } int main() { int u,v; while(~scanf("%d %d",&n,&m) && (n || m)) { for(int i = 1; i <= n*m; i++) edge[i].clear(); memset(Map,-1,sizeof(Map)); scanf("%d",&k); for(int i = 0; i < k; i++) { scanf("%d %d",&u,&v); Map[u][v] = 0; } cnt = 0; int tmp = -1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { tmp++; if(Map[i][j] < 0) { cnt++; addre[cnt] = tmp; Map[i][j] = cnt; } } } //debug(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(Map[i][j] == 0) continue; if(i-1 >= 1 && Map[i-1][j]>0) edge[Map[i][j]].push_back(Map[i-1][j]); if(i+1 <= n && Map[i+1][j]>0) edge[Map[i][j]].push_back(Map[i+1][j]); if(j-1 >= 1 && Map[i][j-1]>0) edge[Map[i][j]].push_back(Map[i][j-1]); if(j+1 <= m && Map[i][j+1]>0) edge[Map[i][j]].push_back(Map[i][j+1]); } } memset(match,-1,sizeof(match)); int ans = 0; for(int i = 1; i <= cnt; i++) { memset(chk,0,sizeof(chk)); ans += dfs(i); } printf("%d\n",ans/2); output(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。