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

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

2024-07-02 12:57:34   224人阅读

题意：在一个m*n的地图上，有空地，草和墙，其中空地和草能穿透攻击光线，而墙不能。每个机器人能够上下左右攻击，问在地图上最多能放多少个不互相攻击的机器人。

 

这个题和HDU 1045 -  Fire Net 很像。很容易联想到对每个点编号然后互相攻击的点连边再求图的最大独立集，但是这个题数据量太多，超时。

换个思路。

将每个机器人可以攻击到的区域在横和竖方向上分开，这样当横和竖攻击方向都确定时就可以确定一个机器人的放置位置，而在同一个横或竖的攻击区域内不可以再放置机器人。

这样我们把原图上的空地按照每行和每列分别编号。注意隔着墙的空地编号不同，但如果隔着的是草则编号相同。

这样就把原图分成了横和竖两个点集，对于原图上的每个空地位置，即对应两个横和竖方向点的边。我们要让每个攻击区域内至多有一个机器人，就是要让每个点至多和一条边相连，这就是求二分图的最大匹配。用匈牙利算法即可。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cstdio>
 7 #include<vector>
 8 using namespace std;
 9 char grid[55][55];
10 bool gl[2505][2505];
11 int gx[55][55],gy[55][55],nx,ny;
12 int m,n;
13 bool vis[2505];
14 int link[2505];
15 void init()
16 {
17     nx=0;
18     ny=0;
19     for(int i=0; i<m; ++i)
20     {
21         bool v=true;
22         for(int j=0; j<n; ++j)
23         {
24             if(grid[i][j]==‘#‘) v=true;
25             else if(grid[i][j]==‘o‘)
26             {
27                 if(v) ++nx;
28                 gx[i][j]=nx;
29                 v=false;
30             }
31         }
32     }
33     for(int j=0; j<n; ++j)
34     {
35         bool v=true;
36         for(int i=0; i<m; ++i)
37         {
38             if(grid[i][j]==‘#‘) v=true;
39             else if(grid[i][j]==‘o‘)
40             {
41                 if(v) ++ny;
42                 gy[i][j]=ny;
43                 v=false;
44             }
45         }
46     }
47     memset(gl,0,sizeof(gl));
48     for(int i=0; i<m; ++i)
49         for(int j=0; j<n; ++j)
50             if(grid[i][j]==‘o‘)
51                 gl[gx[i][j]][gy[i][j]]=true;
52     memset(link,-1,sizeof(link));
53 }
54 bool match(int x)
55 {
56     for(int i=1; i<=ny; ++i)
57         if(gl[x][i]&&!vis[i])
58         {
59             vis[i]=true;
60             if(link[i]==-1||match(link[i]))
61             {
62                 link[i]=x;
63                 return true;
64             }
65         }
66     return false;
67 }
68 int main()
69 {
70     int T,kase=0;;
71     scanf("%d",&T);
72     while(T--)
73     {
74         scanf("%d%d",&m,&n);
75         for(int i=0; i<m; ++i)
76             scanf("%s",grid[i]);
77         init();
78         int ans=0;
79         for(int i=1; i<=nx; ++i)
80         {
81             memset(vis,0,sizeof(vis));
82             if(match(i)) ans++;
83         }
84         printf("Case :%d\n",++kase);
85         printf("%d\n",ans);
86     }
87     return 0;
88 }
View Code

 


联系
我们