poj3026 发表于 2018-04-07 | 分类于 算法 , 图论 , 最小生成树 | 阅读数 次 链接:poj3026 题解 这题很有意思,不用管A,S,当成一样的就好,跑一遍bfs跑出所有A的相关信息,然后套模板,然而我疯狂WA,原因是输入有坑,巨坑, 详情看代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<queue>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=107;const int inf=0x3f3f3f3f;typedef pair<int,int> s;int T,n,m,dis[N][N],d[N][N],cnt,t[N][N],vis[N],ds[N];int dx[5]={0,-1,1,0,0};int dy[5]={0,0,0,-1,1};char g[107][107];queue<s> q;void bfs(int a,int b){ while(!q.empty())q.pop(); memset(t,-1,sizeof(t)); q.push(s(a,b)); t[a][b]=0; while(!q.empty()){ int x=q.front().first; int y=q.front().second; if(d[x][y])dis[d[a][b]][d[x][y]]=t[x][y]; q.pop(); rep(i,1,4){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>m||g[nx][ny]=='#'||t[nx][ny]!=-1)continue; t[nx][ny]=t[x][y]+1; q.push(s(nx,ny)); } }}int prim(int n){ int ans=0; memset(ds,0,sizeof(ds)); memset(vis,0,sizeof(vis)); vis[1]=1; rep(i,1,n)ds[i]=dis[1][i]; rep(i,2,n){ int minm=inf,p; rep(j,1,n)if(!vis[j]&&ds[j]<minm)minm=ds[j],p=j; if(minm==inf)return -1; ans+=minm; vis[p]=1; rep(j,1,n)if(!vis[j]&&ds[j]>dis[p][j])ds[j]=dis[p][j]; } return ans;}int main(){ scanf("%d",&T); while(T--){ char c; cnt=0; scanf("%d%d",&m,&n); memset(d,0,sizeof(d)); do{ //坑点 c=getchar(); }while(c!='\n'); rep(i,1,n){ gets(g[i]+1); rep(j,1,m)if(g[i][j]=='S'||g[i][j]=='A')d[i][j]=++cnt; } rep(i,1,n)rep(j,1,m)if(d[i][j])bfs(i,j); printf("%d\n",prim(cnt)); } return 0;}