最小生成树
每读入一个城市，把他与之前的所有城市做一次link()
link的内容：
1.如果两个城市直接相连，合并他们的集合（并查集）
2.如果两个城市可以搭桥，添加一条边来连接。如果不可以搭桥，什么也不做。
接着循环所有pa[]，如果pa[i]==i，那么这是一个city。这样计算city数量
做kruskal，计算桥的数量和桥的总长度
代码：
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define Size 5005
using namespace std; int n,m;
int city[Size][]; int num=;
int dis=,num_city=,num_bridge=; int pa[Size];
void init(){
for(int i=;i<=n*m;i++){pa[i]=i;}
}
int find(int x){
if(x!=pa[x])pa[x]=find(pa[x]);
return pa[x];
}
bool query(int x,int y){
return find(x)==find(y);
}
void un(int x,int y){
if(query(x,y))return;
pa[find(x)]=find(y);
} struct E{
int a,b,w;
}edge[];
int cnt=;
int add(int a,int b,int w){
cnt++;
edge[cnt].a=a;
edge[cnt].b=b;
edge[cnt].w=w;
} void link(int a,int b){
int cx=abs(city[a][]-city[b][]);
int cy=abs(city[a][]-city[b][]); if(cx<=&&cy<=){un(a,b); return;}
if(cx>=&&cy>=)return; if(cx>=)add(a,b,cx-);
else add(a,b,cy-);
} bool ff(E a,E b){
return a.w<b.w;
} void kruskal(){
sort(edge+,edge++cnt,ff); for(int i=;i<=cnt;i++){
int a=edge[i].a,b=edge[i].b;
if(!query(a,b)){
dis+=edge[i].w;
num_bridge++;
un(a,b);
}
}
} int main(){
cin>>n>>m;
init();
char cc;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
cin>>cc;
if(cc=='#'){
num++;
city[num][]=i; city[num][]=j;
for(int k=;k<num;k++){
link(k,num);
}
}
}
}
// cout<<num<<endl;
// for(int i=1;i<=cnt;i++){
// cout<<edge[i].a<<' '<<edge[i].b<<' '<<edge[i].w<<endl;
// }
for(int i=;i<=num;i++){
if(pa[i]==i)num_city++;
}
kruskal();
cout<<num_city<<endl<<num_bridge<<' '<<dis<<endl;
}