ZOJ1654(二分构图题典例)

题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654

题意：有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

分析：本题也是二分图匹配的一个经典题目。我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人，我们把这些块编上号。同样，把竖直方向的块也编上号。如下图：

把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二分图：

代码：

#include 
#include 
#include using namespace std;
const int N = 1250;char map[N][N];
int col[N][N],row[N][N];
int link[N],head[N];
bool vis[N];
int cnt,n,m;
int R,C;struct Edge
{int to;int next;
};Edge edge[N*N];void Init()
{cnt = 0;memset(head,-1,sizeof(head));memset(col,0,sizeof(col));memset(row,0,sizeof(row));
}void add(int u,int v)
{edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++;
}bool dfs(int u)
{for(int i=head[u]; ~i; i=edge[i].next){int v = edge[i].to;if(!vis[v]){vis[v] = 1;if(link[v] == -1 || dfs(link[v])){link[v] = u;return true;}}}return false;
}int match()
{int ans = 0;memset(link,-1,sizeof(link));for(int i=1; i<=R; i++){memset(vis,0,sizeof(vis));if(dfs(i)) ans++;}return ans;
}int main()
{int T,tt = 1;cin>>T;while(T--){Init();cin>>n>>m;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)cin>>map[i][j];R = C = 1;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(map[i][j] != '#' && row[i][j] == 0){for(int k=j; map[i][k] != '#' && k <= m; k++)row[i][k] = R;++R;}if(map[i][j] != '#' && col[i][j] == 0){for(int k=i; map[k][j] != '#' && k <= n; k++)col[k][j] = C;++C;}}}for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(map[i][j] == 'o' && row[i][j] != 0 && col[i][j] != 0)add(row[i][j],col[i][j]);printf("Case :%d\n",tt++);printf("%d\n",match());}return 0;
}

典型题目：一张残缺的棋盘，用1*2的矩形去覆盖它，要求矩形不互相重叠。求矩形最多可以放多少个。

分析：将棋盘染成黑白相间，黑色方格作为左边的点，白色方格作为右边的点，相邻的黑白方格中间连一条边。对已经建好的图求最大匹配。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！