http://poj.org/problem?id=3026
题意：任意两个字母可以连线，求把所有字母串联起来和最小。
很明显这就是一个最小生成树，不过这个题有毒。他的输入有问题。在输入m和N后面，可能有一大串的空格。就因为这个，我RE都有点懵了，要不是discuss里面有人说输入有问题，我都没注意到这个，原本只用了一个getchar吃掉最后的换行符。没想到之后还有空格。有点小坑。
思路：这个题目如果他给你一个图，那就是最裸的prim了。不过这个题的难点也就是在他给的图你不能用Prim，你只能通过bfs去建立一个你可以新图，让这个新图去使用最小生成树。
#include <string.h>
#include <stdio.h>
#include <queue>
#define inf 0x3f3f3f
#define maxn 300 using namespace std; char mgraph[ maxn ][ maxn ];
int bfsgraph[ maxn ][ maxn ],dist[ maxn ][ maxn ],num[ maxn ][ maxn ],ans,dis[ maxn ];
bool mark[ maxn ][ maxn ],vis[ maxn ]; struct note{
int x,y;
}; void bfs(int x,int y) //我是把图建在bfsgraph里面的。
{
memset( dist , ,sizeof( dist ) );
memset( mark , true , sizeof( mark ) );
bfsgraph[ num[ x ][ y ] ][ num[ x ][ y ] ] = ;
queue<note >s;
note p,q;
p.x = x;
p.y = y;
dist[ x ][ y ] = ;
mark[ x ][ y ] = false;
s.push(p);
while(!s.empty())
{
p = s.front();
s.pop();
if(mark[ p.x + ][ p.y ] && mgraph[ p.x + ][ p.y ] != '#')
{
if( num[ p.x + ][ p.y ]) bfsgraph[ num[ x ][ y ] ][ num[ p.x+ ][ p.y ]] = dist[ p.x ][ p.y ] + ; //如果当前点为字母的话，那么把这个点与起始点的距离给记录。
dist[ p.x + ][ p.y ] = dist[ p.x ][ p.y ] + ;
mark[ p.x + ][ p.y ] = false;
q.x = p.x + ;
q.y = p.y;
s.push(q);
}
if(mark[ p.x ][ p.y - ] && mgraph[ p.x ][ p.y - ] != '#')
{
if( num[ p.x ][ p.y - ]) bfsgraph[ num[ x ][ y ] ][ num[ p.x ][ p.y - ]] = dist[ p.x ][ p.y ] + ;
dist[ p.x ][ p.y - ] = dist[ p.x ][ p.y ] + ;
mark[ p.x ][ p.y - ] = false;
q.x = p.x;
q.y = p.y - ;
s.push(q);
}
if(mark[ p.x ][ p.y + ] && mgraph[ p.x ][ p.y + ] != '#')
{
if( num[ p.x ][ p.y + ]) bfsgraph[ num[ x ][ y ] ][ num[ p.x ][ p.y + ]] = dist[ p.x ][ p.y ] + ; dist[ p.x ][ p.y + ] = dist[ p.x ][ p.y ] + ;
mark[ p.x ][ p.y + ] = false;
q.x = p.x;
q.y = p.y + ;
s.push(q);
}
if(mark[ p.x - ][ p.y ] && mgraph[ p.x - ][ p.y ] != '#')
{
if( num[ p.x- ][ p.y ]) bfsgraph[ num[ x ][ y ] ][ num[ p.x - ][ p.y ]] = dist[ p.x ][ p.y ] + ;
dist[ p.x - ][ p.y ] = dist[ p.x ][ p.y ] + ;
mark[ p.x - ][ p.y ] = false;
q.x = p.x - ;
q.y = p.y;
s.push(q);
}
}
}
int prim(int pos)
{
for(int i = ; i < pos ; i++)
dis[ i ] = inf ; dis[ ] = ;
for(int i = ;i < pos ; i++){
int tep = inf;int k = ;
for(int j = ; j < pos ; j++){
if(vis[ j ]&&dis[ j ]<tep)
{
tep = dis[ j ];
k = j;
}
}
if(tep == inf) return ;
ans += tep;
vis[ k ]=false;
for(int j = ;j < pos ; j++)
if(vis[ j ]&&dis[ j ] > bfsgraph[ k ][ j ])
dis[ j ] = bfsgraph[ k ][ j ];
}
return ;
} int main()
{
// freopen("in.txt","r",stdin);
int t,m,n;
char s[];
scanf("%d",&t);
while( t-- )
{
memset( mgraph , , sizeof( mgraph ) );
memset( bfsgraph , , sizeof( bfsgraph ) );
memset( num , , sizeof( num ) );
scanf("%d%d",&m,&n);
gets(s); //这里要注意，要吃掉m,n后面的空格，不然就等着RE吧。
ans = ;
int pos = ;
note point[ ];
for( int i = ; i < n ; i++ )
gets(mgraph[i]);
for( int i = ; i < n ; i++ )
for( int j = ; j < m ; j++ )
if( mgraph [ i ][ j ] == 'A' || mgraph[ i ][ j ] == 'S')
{
point[ pos ].x = i;
point[ pos ].y = j;
num[ i ][ j ] = pos; //我用num来编号，相当于一个映射，一个点集与一个数集之间的映射，因为要建图。
pos ++;
}
for( int i = ; i < pos ; i++ ) //对每一个点进行bfs。
bfs( point[ i ].x , point[ i ].y );
memset( vis , true , sizeof( vis ) );
prim(pos);
printf("%d\n",ans);
}
return ;
}