首页 > 代码库 > ZOJ 1654 Place the Robots建图思维(分块思想)+二分匹配
ZOJ 1654 Place the Robots建图思维(分块思想)+二分匹配
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654
AC一百道水题,不如AC一道难题来的舒服!
题意:一个n*m地图,*代表草地,#代表墙,o代表空地,要再图中的o处放机器人,机器人可以攻击(上下左右)4个方向,攻击范围无限长,而且机器人不能相互攻击,草地不能放置机器人,且机器人的攻击可以穿过草地,但是机器人的攻击不能穿过墙,比如 “ *o#o ”这一行就可以放两个机器人,” o*oo “ 这一行就只能放一个,问最多能放多少个机器人?
刚学了二分图,二分图的水题做了有几个,不需要来练手了,对于这个题,看懂题意后知道是二分图的最大独立集合,但是难点是怎么建图。
昨天晚上看的这道题目,一点思路也没有,回宿舍后想了又想,想到怎么建图,今天敲了,WA n次,查了一下题解,建图方式没有错,只是我漏了一点就是,只进行了横向分块当做X集合,剩余点默认为Y集合。。。
思路:采用分块的思想进行建图,什么是块?联系题意,块就攻击范围可以达到的就是一块,“ o*oo ”这就是块,而且是一块,“ *o#o ”,这就是两块, 通俗点说就是,地图的这一行被墙隔开且有空地的连续区域称作”块“,当然,按照题意,在一个块中,最多只能放置一个机器人,纵向也是如此分块,对块进行编号,横向分块的所有编号为X集合,纵向的所有编号为Y集合,当然存在同一个” o“点被两次编号过,那么建一条边就好了。
Result Accepted ID | 1654 Language | C++ Time | 60 Memery | 26720 |
include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <math.h> #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 55; const int maxm = 2600; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b int mar[maxn][maxn],mac[maxn][maxn]; int G[maxm][maxm]; int line[maxm]; char MAP[maxn][maxn]; bool vis[maxm]; int X,Y; int DFS(int u) { for(int v = 1;v<=Y;v++) { if(G[u][v]==1 && !vis[v]) { vis[v] = 1; if(line[v]==-1 || DFS(line[v])) { line[v] = u; return 1; } } } return 0; } int K_M() { memset(line,-1,sizeof(line)); int ans = 0; for(int i = 1;i<=X;i++) { init(vis); ans += DFS(i); } return ans; } void Creat_G(int n,int m) { for(int i = 0;i<n;i++) //横向分块当做X集合 { for(int j = 0;j<m;j++) { if(MAP[i][j]=='o') { X++; while(j<m && MAP[i][j]!='#') { mar[i][j]=X;//处于同一块的空地或草地编号是一样的 j++; } } } } for(int i = 0;i<m;i++)//纵向分块当做Y集合 { for(int j = 0;j<n;j++) { if(MAP[j][i]=='o') { Y++; while(j<n && MAP[j][i]!='#') { mac[j][i] = Y; j++; } } } } } int main() { int t,n,m; scanf("%d",&t); for(int Case = 1;Case <=t;Case++) { init(G); init(mar);init(mac); X = 0, Y = 0; scanf("%d%d",&n,&m); for(int i = 0;i<n;i++) scanf("%s",MAP[i]); Creat_G(n,m);//分块 for(int i = 0;i<n;i++) //建图 { for(int j = 0;j<m;j++) { if(MAP[i][j]=='o') { G[mar[i][j]][mac[i][j]] = 1;//构建块与块的连通 } } } int ans = K_M(); printf("Case :%d\n%d\n",Case,ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。