题目大意：

多组测试实例（50），每组测试给你一个图（50*50），然后给你一个Ｓ点和若干个Ａ点（100）。一个小人从点S开始，他在S点或者A点可以分别成多个小人。现在他要访问到每个点，让你求出他要走的最少的距离。
注意： 只有当borg在S点或者找到一个alien之后，它们可以继续以分成若干的小队伍。

思路：

只有在S和A可以分裂，这表示了什么？这表示这个图(无向)，每个顶点(A或S)可以有多个边！然后想到最小生成树，但是每一对点之间的距离怎么计算呢，我觉得就是用广搜确定出来的，就是他们之间的距离(因为有距离)。
这个复杂度可能不小，得算一下：
100个点，两个之间一搜索，100*101/2=5050个搜索，每个图50*50=2500个点（如果全部都要访问一次的话），每组测试实例确定距离需要5000*2500=12,500,000。50组：50* 12,500,000=625,000,000。当然这个是最坏的情况。
然后问题就简化成一个图，求它的最小生成树。我感觉这个图边应该很多，如果用prim枚举点的话，应该是比较划算的。但是仔细一想，因为求最小生成树的过程和n次广搜的过程是并列的，所以慢一点也没关系，反正肯定比n次广搜快，我就写的kruckal。
这次要是还不ac我就要吐血了~

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define maxxy 55
#define maxn 105
#define inf 0x3f3f3f3f


using namespace std;
int n;
int map[maxxy][maxxy]={0};
int dis[maxn][maxn]={0};
int num[maxxy][maxxy];
struct point
{
    int x;
    int y;
}a[maxn];
struct edge
{
    int s;int e;int v;
}b[maxn*maxn]; 
int x,y;
int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int boss[maxn]={0};

int find(int x)
{
    return boss[x]==x?x:boss[x]=find(boss[x]);
}

void match(int a,int b)
{
    int fa=find(a);
    int fb=find(b);
    boss[fa]=fb;
    return;
}


void ceshi1()
{
    for(int i=1;i<=y;i++)
    {
        for(int j=1;j<=x;j++)
        {
            cout<<map[i][j];
        }
        cout<<endl;
    }
}
void ceshi2()
{
    for(int i=1;i<=n;i++)
    {
        cout<<a[i].x<<" "<<a[i].y<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<dis[i][j]<<" ";
        }
        cout<<endl;
    }
}
bool my_cmp(edge a,edge b)
{
    return a.v<b.v;
}
void bfs(int k)//从k号点开始广搜 
{
    bool vis[maxxy][maxxy]={0};
    int v[maxxy][maxxy]={0};
    queue<point>q;
    q.push(a[k]);
    vis[a[k].x][a[k].y]=1;
    v[a[k].x][a[k].y]=0;
    while(!q.empty())
    {
        for(int i=0;i<4;i++)
        {
            point l;
            l.x=q.front().x+move[i][1];
            l.y=q.front().y+move[i][0];
            if(l.x>x||l.x<1||l.y>y||l.y<1)continue;
            if(vis[l.x][l.y])continue;
            if(map[l.x][l.y]==1)continue;
            v[l.x][l.y]=v[q.front().x][q.front().y]+1;
            q.push(l);
            vis[l.x][l.y]=1;
            if(map[l.x][l.y]==2)
            {
                dis[k][num[l.x][l.y]]=v[l.x][l.y];
            }
        }
        q.pop();
    }
}
int my_kruskal()
{
    for(int i=0;i<=n;i++)
    {
        boss[i]=i;
    }
    int s=0;
    int num=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            num++;
            b[num].s=i;
            b[num].e=j;
            b[num].v=dis[i][j];
        }
    }
    sort(b+1,b+num+1,my_cmp);
    for(int i=1;i<=num;i++)
    {
        //cout<<find(b[i].s)<<" "<<find(b[i].e)<<endl;
        if(find(b[i].s)==find(b[i].e))continue;
        match(b[i].s,b[i].e);
        s+=b[i].v;
    }
    return s;
}
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        char c;
        scanf("%d %d",&x,&y);
        while(c!='\n')
        {
            scanf("%c",&c);
        }
        n=1;
        memset(map,0,sizeof(map));
        memset(dis,0x3f,sizeof(dis));
        for(int i=1;i<=y;i++)
        {
            for(int j=0;j<=x;j++)//墙1，外星人2，空位0 
            {
                scanf("%c",&c);
                if(c=='#')map[j+1][i]=1;
                if(c=='A')
                {
                    map[j+1][i]=2;
                    n++;
                    a[n].x=j+1;a[n].y=i;
                    num[j+1][i]=n;
                }
                if(c=='S')
                {
                    map[j+1][i]=2;
                    a[1].x=j+1;a[1].y=i;
                    num[j+1][i]=1;
                }
            }
        }
        //ceshi1();
        for(int i=1;i<=n;i++)
        {
            bfs(i);
        }
        //ceshi2();
        cout<<my_kruskal()<<endl;
    }
}

另外附上以前寒假时候写的错的代码，也许有一天我真的会去查查以前是怎么错的吧，主要是实在不舍得删啊。这一段你们就不要看了。。。。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<string.h>
#define xy_max 65
#define N 120
#define inf 0x3f3f3f3f
using namespace std;
struct point
{
    int x;
    int y;
}poi[N]={0};
int x,y; 
int n;//点的个数 
char map[xy_max][xy_max];
int dis[N][N]={0};//1号点为S
int deep[xy_max][xy_max]={0};//点ij到原点的距离 
bool vis[xy_max][xy_max]={0};
int mincost[N]={0};
bool inside[N]={0};
void input()
{
    memset(map,0,sizeof(map));
    n=2;
    cin>>x>>y;
    char c;
    scanf("%c",&c);//注意要读取数字行的换行符 
    for(int i=1;i<=y;i++)
    {
        for(int j=1;j<=x+1;j++)
        {
            scanf("%c",&map[i][j]);
            if(map[i][j]=='S')
            {
                poi[1].x=j;
                poi[1].y=i;
            }
            if(map[i][j]=='A')
            {
                poi[n].x=j;
                poi[n].y=i;
                n++;
            }
        }
    }
}

void bfs(int v)//对v号点进行dfs 
{
    point k=poi[v];
    int fx[4]={-1,0,1,0};
    int fy[4]={0,1,0,-1};
    memset(deep,0,sizeof(deep));
    memset(vis,0,sizeof(vis));
    queue<int>qx;
    queue<int>qy;
    qx.push(k.x);
    qy.push(k.y);
    deep[k.y][k.x]=0;
    vis[k.y][k.x]=1;
    while(1)
    {

        if(qx.empty()&&qy.empty())break;
        for(int i=0;i<4;i++)//向四个方向扩展 
        {
            if(qy.front()+fy[i]<=0||qy.front()+fy[i]>y||qx.front()+fx[i]<=0||qx.front()+fx[i]>x)continue;
            if(vis[qy.front()+fy[i]][qx.front()+fx[i]])continue;
            if(map[qy.front()+fy[i]][qx.front()+fx[i]]=='#')continue;
            deep[qy.front()+fy[i]][qx.front()+fx[i]]=deep[qy.front()][qx.front()]+1;
            vis[qy.front()+fy[i]][qx.front()+fx[i]]=1;
            qx.push(qx.front()+fx[i]);
            qy.push(qy.front()+fy[i]);
        }
        qx.pop();
        qy.pop();
    }
    for(int i=1;i<n;i++)
    {
        dis[v][i]=deep[poi[i].y][poi[i].x];
    }

} 

void ceshi1()
{
    for(int i=1;i<n;i++)
    {
        cout<<poi[i].y<<poi[i].x; 
        cout<<endl;
    }
} 
void ceshi2()
{
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)cout<<dis[i][j];
        cout<<endl;
    }
}
int numout()
{
    int s=0;
    for(int i=1;i<n;i++)
    {
        if(inside[i]==0)s++;
    }
    return s;
}
int my_prim()
{
    int v=1;
    int s=0;
    memset(inside,0,sizeof(inside));
    inside[1]=1;
    for(int i=1;i<n;i++)
    {
        mincost[i]=dis[1][i];
    }
    while(1)
    {
        if(numout()==0)break;
        int min=inf;
        for(int i=1;i<n;i++)//找到即将入图的点号v 
        {
            if(inside[i]==1)continue;
            if(min>mincost[i])
            {
                min=mincost[i];
                v=i;
            }
        }
        s=s+min;
        inside[v]=1;
        for(int i=1;i<n;i++)
        {
            if(inside[i]==1)continue;
            if(mincost[i]>dis[v][i])
            {
                mincost[i]=dis[v][i];
            }
        } 

    }
    return s;
}


int main()
{
    int cs=0;
    cin>>cs;
    while(cs--)
    {
        input();
        for(int i=1;i<n;i++)bfs(i);
        //ceshi2();
        //ceshi1();
        cout<<my_prim()<<endl;
    }
}
/* 8 6 5 ##### #A#A## # # A# #S ## ##### 7 7 ##### #AAA### # A# # S ### # # #AAA### ##### 6 5 ##### #A#A## # # A# #S ## ##### 7 7 ##### # ### # # # S ### # # # ### ##### */

后记：

出问题可以先偷偷看下discuss。这道题输入数据中输入地图大小的两个数所在的那一行，两个数后面可能会有若干空格。