Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals

## 感谢discuss ，水过

Posted by ALLACS at 2018-01-09 14:36:38 on Problem 3026
```//bfs+kruskal
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int>PII;
const int maxv=110;
const int maxe=6000+5;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
struct Edge{
int from,to,weight;
};
bool operator<(const Edge &E1,const Edge &E2)
{
return E1.weight<E2.weight;
}
Edge edges[maxe];
int parent[maxv];
int find(int x)
{
return x==parent[x]?x:parent[x]=find(parent[x]);
}
char str[maxv][maxv];
PII ps[maxv];
int dist[maxv][maxv];
int n,m;
void bfs(int x,int y)
{
queue<PII>pq;
while(!pq.empty()) pq.pop();
pq.push(PII(x,y));
memset(dist,-1,sizeof(dist));
dist[x][y]=0;
while(!pq.empty())
{
PII k=pq.front();
pq.pop();
for(int i=0;i<4;i++)
{
int nx=k.first+dx[i],ny=k.second+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n&&str[nx][ny]!='#'&&dist[nx][ny]==-1) {
pq.push(PII(nx,ny));
dist[nx][ny]=dist[k.first][k.second]+1;
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
char temp[maxv];
scanf("%d%d",&n,&m);        //n为列数，m为行数
gets(temp);                     //输入两个整数后有空格
int ans=2;
for(int i=0;i<m;i++)
{
gets(str[i]);
for(int j=0;j<n;j++)
{
if(str[i][j]=='A') {
ps[ans].first=i;
ps[ans].second=j;
ans++;
}
else if(str[i][j]=='S') {
ps[1].first=i;
ps[1].second=j;
}
}
}
//bfs并建图
int cnt=0;
for(int i=1;i<ans-1;i++)
{
bfs(ps[i].first,ps[i].second);
//根据dist数组建图
for(int j=i+1;j<ans;j++)
{
edges[cnt].from=i;
edges[cnt].to=j;
edges[cnt].weight=dist[ps[j].first][ps[j].second];
cnt++;
}
}
sort(edges,edges+cnt);
int sum=0;
for(int i=1;i<=ans-1;i++)
parent[i]=i;
for(int i=0;i<cnt;i++)
{
int p1=find(edges[i].from);
int p2=find(edges[i].to);
if(p1==p2) continue;
parent[p1]=p2;
sum+=edges[i].weight;
}
printf("%d\n",sum);
}
return 0;
}
```

Followed by: