【POJ - 3026】Borg Maze（bfs预处理 + 最小生成树，建图）
题干：
The Borg is an immensely powerful race of enhanced humanoids from the delta quadrant of the galaxy. The Borg collective is the term used to describe the group consciousness of the Borg civilization. Each Borg individual is linked to the collective by a sophisticated subspace network that insures each member is given constant supervision and guidance.
Your task is to help the Borg (yes, really) by developing a program which helps the Borg to estimate the minimal cost of scanning a maze for the assimilation of aliens hiding in the maze, by moving in north, west, east, and south steps. The tricky thing is that the beginning of the search is conducted by a large group of over 100 individuals. Whenever an alien is assimilated, or at the beginning of the search, the group may split in two or more groups (but their consciousness is still collective.). The cost of searching a maze is definied as the total distance covered by all the groups involved in the search together. That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3.
Input
On the first line of input there is one integer, N <= 50, giving the number of test cases in the input. Each test case starts with a line containg two integers x, y such that 1 <= x,y <= 50. After this, y lines follow, each which x characters. For each character, a space `` '' stands for an open space, a hash mark ``#'' stands for an obstructing wall, the capital letter ``A'' stand for an alien, and the capital letter ``S'' stands for the start of the search. The perimeter of the maze is always closed, i.e., there is no way to get out from the coordinate of the ``S''. At most 100 aliens are present in the maze, and everyone is reachable.
Output
For every test case, output one line containing the minimal cost of a succesful search of the maze leaving no aliens alive.
Sample Input
2 6 5 ##### #A#A## # # A# #S ## ##### 7 7 ##### #AAA### # A# # S ### # # #AAA### #####
Sample Output
8 11
题目大意：
这个题意是真难懂啊、、、
在一个迷宫中有很多外星人A，某个人在S点开始去抓捕，抓捕到外星人后这个人可以分身为任意个（也可以不分身），求把所有外星人抓完所用的最小距离，距离包括分身走的距离（即所有的距离都算上，比如：两个分身同时走三步，那么走的距离就是6，而不是3），在迷宫之中只能向东南西北四个方向移动。
换种说法：
给你一个地图，地图中A代表外星人，S代表出发点，从S点出发，在起点S 或是 每遇到一个A点 便可不分裂或是分裂成多个。求把所有A都吃完需要多少步。注意不要以为当前点随时都能分裂，而是只有在S或是遇到A才能分裂。
解题报告：
注意这题样例 n m 和字符串之间可能有一行空行（而不一定是一个空格）真tm格式、、所以getchar会WA的。。
因为不难发现，既然这个题意的话，那么起点在哪并没有怎么所谓了，因为S的所有特点和A的所有特点是完全相同的，所以可以把S点也看成是一个A点，那么题意转化成：从一个A点出发，在所有A点相连的路径中选择一些路径，使得走过的路最小。
那么解法很显然了，假设有tot个S和A，那么用bfs构造出这tot个点之间的距离，然后求个MST就好，因为稠密图而且是完全图所以首选prim。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 200 + 5;
const int INF = 0x3f3f3f3f;
int n,m;
char s[MAX][MAX];
int bk[MAX][MAX],cost[MAX][MAX],tot;
bool vis[MAX][MAX];
int nx[4] = {0,1,0,-1};
int ny[4] = {1,0,-1,0};
struct Node {
int x,y,t;
Node(int x=0,int y=0,int t=0):x(x),y(y),t(t){}
};
void bfs(int stx,int sty) {
int id1 = bk[stx][sty];
queue<Node> q;
q.push(Node(stx,sty,0));
memset(vis,0,sizeof vis);
vis[stx][sty]=1;
while(!q.empty()) {
Node cur = q.front();q.pop();
int id2 = bk[cur.x][cur.y];
if(bk[cur.x][cur.y]) cost[id1][id2] = cur.t;
for(int k = 0; k<4; k++) {
int tx = cur.x+nx[k];
int ty = cur.y+ny[k];
if(tx<0||tx>n||ty<1||ty>m) continue;
if(vis[tx][ty] || s[tx][ty] == '#') continue;
vis[tx][ty] = 1;
q.push(Node(tx,ty,cur.t+1));
}
}
}
int VIS[MAX*MAX],dis[MAX*MAX];
int prim() {
int res = 0;
for(int i = 1; i<=tot; i++) dis[i] = INF,VIS[i] = 0;
dis[1] = 0;
while(1) {
int minv,minw=INF;
for(int i = 1; i<=tot; i++) {
if(VIS[i] == 0 && dis[i] < minw) minw = dis[i],minv = i;
}
if(minw == INF) break;
VIS[minv] = 1;
for(int i = 1; i<=tot; i++) {
if(VIS[i] == 0 && dis[i] > cost[minv][i]) dis[i] = cost[minv][i];
}
res += dis[minv];
}
return res;
}
int main()
{
int t;
cin>>t;
while(t--) {
tot=0;
memset(bk,0,sizeof bk);
memset(cost,0,sizeof cost);
scanf("%d%d",&m,&n);
string qq;getline(cin,qq);
for(int i = 1; i<=n; i++) {
cin.getline(s[i]+1,1005);
for(int j = 1; j<=m; j++) {
if(s[i][j] == 'S' || s[i][j] == 'A') bk[i][j] = ++tot;
}
}
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
if(bk[i][j]) bfs(i,j);
}
}
printf("%d\n",prim());
}
return 0 ;
} 刚开始WA在数组就开了50*50这么大，导致cost数组也开了[50][50],但是其实应该[2501][2501]，但是其实这题说了最多100个外星人，所以可以开[105][105]就够了。
查看6道真题和解析