最小生成树

每读入一个城市，把他与之前的所有城市做一次link()

link的内容：

1.如果两个城市直接相连，合并他们的集合（并查集）

2.如果两个城市可以搭桥，添加一条边来连接。如果不可以搭桥，什么也不做。

接着循环所有pa[]，如果pa[i]==i，那么这是一个city。这样计算city数量

做kruskal，计算桥的数量和桥的总长度

 

代码：

#include
     
      #include
      
       #include
       
        #define Size 5005using namespace std;int n,m;int city[Size][2]; int num=0;int dis=0,num_city=0,num_bridge=0;int pa[Size];void init(){    for(int i=1;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[100005];int cnt=0;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][0]-city[b][0]);    int cy=abs(city[a][1]-city[b][1]);        if(cx<=1&&cy<=1){un(a,b); return;}    if(cx>=2&&cy>=2)return;        if(cx>=2)add(a,b,cx-1);    else add(a,b,cy-1);}bool ff(E a,E b){    return a.w
        
         >n>>m;    init();    char cc;    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            cin>>cc;            if(cc=='#'){                num++;                city[num][0]=i; city[num][1]=j;                for(int k=1;k