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

?

題意：有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機器人，使它們不能互相攻擊。

分析：本題也是二分圖匹配的一個經典題目。我們將每一行，每一列被墻隔開，且包含空地的連續區域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人，我們把這些塊編上號。同樣，把豎直方向的塊也編上號。如下圖：

? ? ? ?

把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。于是，問題轉化成這樣的一個二分圖：

代碼：

#include <iostream> #include <string.h> #include <stdio.h>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的矩形去覆蓋它，要求矩形不互相重疊。求矩形最多可以放多少個。

分析：將棋盤染成黑白相間，黑色方格作為左邊的點，白色方格作為右邊的點，相鄰的黑白方格中間連一條邊。對已經建好的圖求最大匹配。

總結

以上是生活随笔為你收集整理的ZOJ1654(二分构图题典例)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。