POJ 3026 Borg Maze （最小生成樹）

Description

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      

題意

從 S 出發，去到達每一個 A ，求最小的總路徑長度，空格是空地，# 是牆，并且在走的過程中我們可以在 S 或 A 點分裂，也就是從該點可以延伸出多條路徑到其他點，但是每一次隻能讓其中的一個繼續行走。

思路

既然每一個 S 或 A 處才可以分裂，并且隻能讓其中一個行走，求最小的路徑長度，便是一棵包含所有 S 或 A 點的樹。

那麼，首先通過bfs枚舉每一個點到其他點的最短路徑長度，然後建立這樣一個完全圖。（其實還有比枚舉更好的辦法，但是因為點數目較少，枚舉便可以啦）

然後在這一個完全圖中求一顆最小生成樹，最小生成樹所有邊長度的和便是總路徑長度。

AC 代碼

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#define inf (1<<25)
using namespace std;

int mapp[55][55];
int mv[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
bool vis[55][55];
int parent[255];   //父親節點，當值為-1時表示根節點

struct node
{
    int x,y,time;
    node() {};
    node(int x,int y,int time)
    {
        this->x=x;
        this->y=y;
        this->time=time;
    }
};
struct eage     //邊的結構體，u、v為兩端點，w為邊權值
{
    int u, v, w;
    eage() {};
    eage(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
} EG[250*250];
int stop,x,y,etop;

void bfs(int ix,int iy)
{
//    printf("bfs %d,%d\n",ix,iy);
    memset(vis,false,sizeof(vis));      //所有點都沒有被通路
    queue<node*>sk;
    vis[ix][iy]=true;
    sk.push(new node(ix,iy,0));         //初始點入隊
    while(!sk.empty())
    {
        node* p=sk.front();
        sk.pop();
        if(!(p->x==ix&&p->y==iy)&&mapp[p->x][p->y]>0)   //如果找到其他點
        {
            EG[etop++]=eage(mapp[ix][iy],mapp[p->x][p->y],p->time); //加邊
//            printf("%d -> %d ,%d\n",mapp[ix][iy],mapp[p->x][p->y],p->time);
        }
        for(int i=0; i<4; i++)          //移動
        {
            int xi=p->x+mv[i][0],yi=p->y+mv[i][1];
            if(xi<0||xi>=y||yi<0||yi>=x||mapp[xi][yi]<0||vis[xi][yi])continue;  //不合理的
            vis[xi][yi]=true;
            sk.push(new node(xi,yi,p->time+1));
        }
        free(p);
    }
}

bool cmp(eage a, eage b)    //排序調用
{
    return a.w < b.w;
}

int Find(int x)     //尋找根節點，判斷是否在同一棵樹中的依據
{
    if(parent[x] == -1) return x;
    return Find(parent[x]);
}

void Kruskal()      //Kruskal算法，parent能夠還原一棵生成樹，或者森林
{
    memset(parent, -1, sizeof(parent));
    int cnt = stop,ans=0;        //初始時根節點數目為n個
    sort(EG, EG+etop, cmp);    //按權值将邊從小到大排序
    for(int i = 0; i < etop; i++)     //按權值從小到大選擇邊
    {
        if(cnt == 1) break;     //當根節點隻有1個時，跳出循環
        int t1 = Find(EG[i].u), t2 = Find(EG[i].v);
        if(t1 != t2)    //若不在同一棵樹種則選擇該邊，
        {
            ans += EG[i].w;
            parent[t1] = t2;
            cnt--;      //每次合并，減少一個根節點
        }
    }
    printf("%d\n",ans);
}

int main()
{
    int n;
    char str[55];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&x,&y);
        gets(str);                  //這裡可能會出現很多空格
        stop=etop=0;
        memset(mapp,-1,sizeof(mapp));
        for(int i=0; i<y; i++)
        {
            gets(str);
            for(int j=0; j<x; j++)
                if(str[j]=='A'||str[j]=='S')
                    mapp[i][j]=++stop;
                else if(str[j]==' ')mapp[i][j]=0;
        }
        for(int i=0; i<y; i++)
            for(int j=0; j<x; j++)
                if(mapp[i][j]>0)    //從 'A' 或 'S' 開始
                    bfs(i,j);
        Kruskal();
    }
    return 0;
}