很裸的一道最小生成树题目，就是建立map[][]后直接套模板。。。。

求最小生成树中的最大权值。。。做这个题时犯了个很2的错误，贡献了好几次WA。。最后重敲了一遍A了。。不说那2的错误了。

裸的最小生成树

注意这里the group may split in two or more groups 应为他在最小生成树专题里，看看题目就可以理解转换成最小生成树求解。如果没有分类我想只有那些大牛们才能想到吧。。

中出所有的A,S点，然后bfs求出任意两点的距离，然后套最小生成树模板。。。才开始RE了一下。。。因为A点至多100个在加上A101我直接开成55了。。这道题目最坑爹的地方在DIscuss里面有。唉。。不说了。。。

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #define maxn 55 #define inf 99999999 using namespace std; struct node {
    int x,y; int val; }; int map[maxn][maxn],dis[120]; int c[120][120]; bool vt[120],flag[maxn][maxn]; int n,m,ans; char str[maxn][maxn]; int knum; int dir[4][2] = {
    {
    0,-1},{-1,0},{
    0,1},{
    1,0}}; void bfs(int x,int y,int val) {
        node cur,nt;     queue
          
           q; while (!q.empty()) q.pop();     cur.x = x;cur.y = y;cur.val = val;     q.push(cur); while (!q.empty())     {
    // puts("@@@@");         cur = q.front(); q.pop(); for (int i = 0; i < 4; ++i)         {
    int p1 = cur.x + dir[i][0]; int p2 = cur.y + dir[i][1]; if (!flag[p1][p2] && map[p1][p2] >= 0)//可以使空格 A， S             {
                    flag[p1][p2] = true;                 nt.x = p1; nt.y = p2;                 nt.val = cur.val + 1; if (map[p1][p2] > 0)//保证必须是A S                 {
    int xx = map[p1][p2]; int yy = map[x][y];                     c[xx][yy] = c[yy][xx] = nt.val;                 }                 q.push(nt);             }         }     } } void prim() {
    int i,j,k,min; for (i = 1; i < knum; ++i)     {
            dis[i] = c[1][i] ;         vt[i] = false;     }     vt[1] = true; ans = 0; for (k = 2; k < knum; ++k)     {
            j = 0; min= inf; for (i = 2; i < knum; ++i)         {
    if (!vt[i] && dis[i] < min)             {
                   j = i; min = dis[i];             }         }         vt[j] = true;         ans += min; for (i = 2; i < knum; ++i)         {
    if (!vt[i] && dis[i] > c[i][j])              dis[i] = c[i][j];         }     } } int main() {
    int i,j,t;    cin>>t; char dd[100]; while (t--)    {
           scanf("%d%d",&m,&n);        gets(dd);//最坑爹的地方。。。多个空格        for (i = 0; i < n; ++i)        gets(str[i]);        knum = 1; for (i = 0; i < n; ++i)//转换成int型矩阵，然后编号        {
    for (j = 0; j < m; ++j)            {
    if (str[i][j] == '#')                map[i][j] = -1; else if (str[i][j] == ' ')                map[i][j]  = 0; else if (str[i][j] == 'A' || str[i][j] == 'S')                {
                       map[i][j] = knum++;                }            }        } //printf("%d\n",knum);        for(i = 0; i < knum;  ++i)//初始化最小生成树的图        {
    for (j = 0; j < knum; ++j)            {
    if (i == j) c[i][j] = 0; else c[i][j] = inf;            }        } for (i = 0; i < n; ++i)//bfs寻找任意两点之间的距离        {
    for (j = 0; j < m; ++j)            {
    if  (str[i][j] == 'A' || str[i][j] == 'S')                {
                       memset(flag,false,sizeof(flag));                    flag[i][j] = true;                    bfs(i,j,0);                }            }        }         prim();//求最小生成树         printf("%d\n",ans);    } return 0; }