首页 > 代码库 > ZOJ 1654 Place the Robots 二分图最大匹配

ZOJ 1654 Place the Robots 二分图最大匹配

2024-07-15 01:31:12   221人阅读

唉，又是神一样的建模，表示完全想不到。

题意是给你一块地，上面有空地，草地，障碍三种地形，然后让你在上面放机器人，机器人只能放在空地上。机器人会向上下左右四个方向发出攻击，机器人的攻击可以穿过草地但是无法穿过障碍。问你在不会是机器人相互攻击的前提下，最多能放多少个机器人。

我觉得大致的思路应该是这样的，首先会想当然的想到把能够相互攻击到的空地连边，然后求最大独立集，但最大独立集不好求，所以要想办法把它转化成最大匹配问题。

所以要想办法把空地变成边，首先一块空地肯定是有他的横坐标和纵坐标，可以表示成相交的两条在图上的路径的形式。并且有，如果两个空地在同一行或者同一列，如果中间没有障碍物相隔的话，那么肯定只能最多放一个机器人，就把他当成是一块空地来处理。这样我们就能把原来按照行和列进行分割和标号了。然后遍历所有行和列的交点，如果这个交点是空地的话，就建立一条从这一点行的编号到这一点列的编号的双向边，一个二分图就建立起来了。

二分图上的每一个点表示的是行上或者列上的一个区域，这个区域只能放置一个机器人，并且相连的两个点只能放一个机器人，这样就成功转化成求最大匹配的问题了。

另外，要注意这题的输出时非主流的Case :1,冒号在前面，一开始写成 Case 1:狂WA，真是囧

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 61;const int maxk = maxn * maxn;char buf[maxn][maxn];int bx[maxk],by[maxk],n,m,cntx,cnty;int xid[maxn][maxn],yid[maxn][maxn];bool g[maxk][maxk],vis[maxk];int dfs(int now) {    for(int i = 1;i <= cnty;i++) if(g[now][i] && !vis[i]) {        vis[i] = true;        if(!by[i] || dfs(by[i])) {            bx[now] = i; by[i] = now;            return 1;        }    }    return 0;}int solve() {    int ret = 0;    memset(bx,0,sizeof(bx));    memset(by,0,sizeof(by));    for(int i = 1;i <= cntx;i++) if(!bx[i]) {        memset(vis,0,sizeof(vis));        ret += dfs(i);    }    return ret;}int main() {    int T; scanf("%d",&T);    for(int kase = 1;kase <= T;kase++) {        scanf("%d%d",&n,&m);        for(int i = 1;i <= n;i++) scanf("%s",buf[i] + 1);        //build-graph        memset(xid,0,sizeof(xid));        memset(yid,0,sizeof(yid));        memset(g,0,sizeof(g));        cntx = cnty = 0;        for(int i = 1;i <= n;i++) {            int flag = 0;            for(int j = 1;j <= m;j++) {                if(buf[i][j] == ‘o‘) {                    if(flag == 0) cntx++,flag = 1;                    xid[i][j] = cntx;                } else if(buf[i][j] == ‘#‘) flag = 0;            }        }        for(int j = 1;j <= m;j++) {            int flag = 0;            for(int i = 1;i <= n;i++) {                if(buf[i][j] == ‘o‘) {                    if(!flag) cnty++,flag = 1;                    yid[i][j] = cnty;                } else if(buf[i][j] == ‘#‘) flag = 0;            }        }        for(int i = 1;i <= n;i++) {            for(int j = 1;j <= m;j++) if(xid[i][j] && yid[i][j]) {                g[xid[i][j]][yid[i][j]] = true;            }        }        int ans = solve();        printf("Case :%d\n%d\n",kase,ans);    }    return 0;}

 


联系
我们