題意：給定一個方格，格子中的每點由空地，草地和墻組成，每個空地可以放置一個機器人，每個機器人能夠向四個方向掃射激光，所以要給定一種方案能夠在棋盤上放置足夠多的機器人。激光可以穿過草地但是不能夠穿過墻。

解法：這題其實就是經典的二分匹配構圖題，做法是將行和列進行拆分，也即如果某一行中有一堵墻，那么將墻前面和后面視為不同的一行，對列進行同樣的處理，那么每個空地就需要獲得一個新的行和列屬性，通過遍歷整個圖來給每一塊空地分配一個行和列號。分配要盡可能的緊湊。對于任何一塊空地，要占用一個行和一個列（意味著該行和該列內不能夠再容下其他空地）對于每一塊空地，將其所對應的行號和列號分為圖兩個部分，構成二分圖。二分圖中邊的含義就是某一行和某一列匹配，也即一組邊對應一組坐標，對應一個能夠放置棋子的空地，最大匹配即為在每一行和每一列最多匹配一次的情況下最多放置多少個棋子。

采用以下方式進行編號：

?

行和列編號數組不小心使用char數組，段錯誤到崩潰......

代碼如下：

View Code #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std;const int MaxN = 60; int N, M, rnum, cnum; char mp[MaxN][MaxN]; int rn[MaxN][MaxN], cn[MaxN][MaxN]; // rn用來記錄某一個點在拆行后的行號，同理cn用來記錄某一個點在拆列后的列號void getr() { // 該函數能夠為每一個空地分配拆行后的行號memset(rn, 0xff, sizeof (rn));rnum = 1;for (int i = 0; i < N; ++i) {for (int j = 0; j < M; ++j) {if (mp[i][j] == 'o') {rn[i][j] = rnum;while (++j < M && mp[i][j] != '#') {if (mp[i][j] == 'o') rn[i][j] = rnum;}// 處理位于同一行的并以空地開頭的行視為一行，其中為某些草地具有連通性 --j, ++rnum;}} } }void getc() { // 該函數能夠為一塊空地分配一個拆列后的列號 memset(cn, 0xff, sizeof (cn));cnum = 1;for (int j = 0; j < M; ++j) {for (int i = 0; i < N; ++i) {if (mp[i][j] == 'o') {cn[i][j] = cnum;while (++i < N && mp[i][j] != '#') {if (mp[i][j] == 'o') cn[i][j] = cnum; }--i, ++cnum;}}} }char G[MaxN*MaxN][MaxN*MaxN], vis[MaxN*MaxN]; int match[MaxN*MaxN];void build() {getr();getc();memset(G, 0, sizeof (G));for (int i = 0; i < N; ++i) {for (int j = 0; j < M; ++j) {if (mp[i][j] == 'o') {G[rn[i][j]][cn[i][j]] = 1;// 一塊空地占用一行和一列 }}} }bool path(int u) {for (int i = 1; i < cnum; ++i) {if (!G[u][i] || vis[i]) continue;vis[i] = 1;if (!match[i] || path(match[i])) {match[i] = u;return true;}}return false; }int query() {int ret = 0;memset(match, 0, sizeof (match));for (int i = 1; i < rnum; ++i) {memset(vis, 0, sizeof (vis));if (path(i)) {++ret;}}return ret; }/* 5 5 o***# *###* oo#oo ***#o #o**o4 */int main() {int T, ca = 0;scanf("%d", &T);while (T--) {scanf("%d %d", &N, &M);for (int i = 0; i < N; ++i) {scanf("%s", mp[i]);}printf("Case :%d\n%d\n", ++ca, (build(), query()));}return 0; }

?

?

貼個最大團TLE代碼：

View Code #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std;int N, M, nd[2505], idx, G[2505][2505]; char mp[55][55];bool check(int a, int b) {int x1 = nd[a]/N, y1 = nd[a]%N;int x2 = nd[b]/N, y2 = nd[b]%N;if (x1 != x2 && y1 != y2) return true;if (x1 == x2) { // 如果是在同一行for (int i = y1+1; i < y2; ++i) {if (mp[x1][i] == '#') {return true;}}}else if (y1 == y2) {for (int i = x1+1; i < x2; ++i) {if (mp[i][y1] == '#') {return true;}}}return false; }void build() {memset(G, 0, sizeof (G));for (int i = 0; i < idx; ++i) {for (int j = i+1; j < idx; ++j) {G[i][j] = G[j][i] = check(i, j);}} }int ret, cnt[2505], st[2505];void dfs(int x, int num) {for (int i = x+1; i < idx; ++i) {if (!G[x][i]) continue;if (cnt[i] + num <= ret) return;int flag = true;for (int j = 0; j < num; ++j) {if (!G[i][st[j]]) {flag = false;break;}}if (flag) {st[num] = i;dfs(i, num+1);}}if (num > ret) {ret = num;} }int query() {ret = 0;for (int i = idx-1; i >= 0; --i) {st[0] = i;dfs(i, 1);cnt[i] = ret;}return ret; }int main() {int T, ca = 0;scanf("%d", &T);while (T--) {scanf("%d %d", &N, &M);idx = 0;for (int i = 0; i < N; ++i) {scanf("%s", mp[i]);for (int j = 0; j < M; ++j) {if (mp[i][j] == 'o') {nd[idx++] = i*N+j;}}}build();printf("Case :%d\n%d\n", ++ca, query());}return 0; }

?

轉載于:https://www.cnblogs.com/Lyush/archive/2013/04/03/2997381.html

總結

以上是生活随笔為你收集整理的ZOJ-1654 Place the Robots 拆行拆列构图+二分匹配 Or 最大独立点集+TLE的全部內容，希望文章能夠幫你解決所遇到的問題。

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