题目链接：http://poj.org/problem?id=3026

题意：题意就是从起点开始可以分成多组总权值就是各组经过的路程，每次到达一个‘A‘点可以继续分组，但是在路上不能分组

于是就是明显的最小生成树，点与点的距离要用bfs或者dfs求一下。这题bfs要稍微优化一下。不能下暴力的bfs就是两点两点之间

bfs这样会有很多重复的查询会超时，所以要一次性的bfs找到一个点就bfs到底。

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <queue>using namespace std;int x , y , num , pos[200][200] , cost[200][200] , f[200] , dr[4][2] = {0 , 1 , 0 , -1 , 1 , 0 , -1 , 0};char s[60][60] , cp[10];void init() {    for(int i = 0 ; i <= num ; i++) {        f[i] = i;    }}int find(int x) {    if(x == f[x])        return x;    int tmp = find(f[x]);    return f[x] = tmp;}struct TnT {    int x , y , step;};struct node {    int x , y , val;}nodes[40000];bool cmp(node a , node b) {    return a.val < b.val;}bool vis[110][110] , have[110][110];void bfs(int xx , int yy) {    memset(vis , false , sizeof(vis));    queue<TnT>q;    vis[xx][yy] = true;    TnT gg , gl;    gg.x = xx , gg.y = yy , gg.step = 0;    q.push(gg);    while(!q.empty()) {        gg = q.front();        q.pop();        if(pos[gg.x][gg.y] != -1) {            cost[pos[xx][yy]][pos[gg.x][gg.y]] = gg.step;        }        for(int i = 0 ; i < 4 ; i++) {            gl.x = gg.x + dr[i][0];            gl.y = gg.y + dr[i][1];            gl.step = gg.step + 1;            if(gl.x >= 0 && gl.x < y && gl.y >= 0 && gl.y < x && s[gl.x][gl.y] != ‘#‘ && !vis[gl.x][gl.y]) {                vis[gl.x][gl.y] = true;                q.push(gl);            }        }    }}int main() {    int t;    scanf("%d" , &t);    while(t--) {        scanf("%d%d" , &x , &y);        gets(cp);        for(int i = 0 ; i < y ; i++) {            for(int j = 0 ; j < x ; j++) {                pos[i][j] = -1;                cost[i][j] = -1;            }        }        num = 0;        for(int i = 0 ; i < y ; i++) {            gets(s[i]);            for(int j = 0 ; j < x ; j++) {                if(s[i][j] == ‘A‘ || s[i][j] == ‘S‘) {                    pos[i][j] = num++;                }            }        }        for(int i = 0 ; i < y ; i++) {            for(int j = 0 ; j < x ; j++) {                if(s[i][j] == ‘A‘ || s[i][j] == ‘S‘) {                    bfs(i , j);                }            }        }        init();        int count = 0;        for(int i = 0 ; i < num ; i++) {            for(int j = i + 1 ; j < num ; j++) {                if(cost[i][j] != -1) {                    nodes[count].x = i , nodes[count].y = j , nodes[count].val = cost[i][j];                    count++;                }            }        }        sort(nodes , nodes + count , cmp);        int sum = 0 , temp = 0;        for(int i = 0 ; i < count ; i++) {            int a = find(nodes[i].x) , b = find(nodes[i].y);            if(a != b) {                f[a] = b;                sum += nodes[i].val;                temp++;            }            if(temp == num - 1)                break;        }        printf("%d\n" , sum);    }    return 0;}

poj 3026 Borg Maze（最小生成树+bfs）