Constructing Roads POJ - 2421 最小生成树之Kruskal算法

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 //u表示起点，v表示终点，cost表示花费
 22 struct node
 23 {
 24     int u,v;
 25     double cost;
 26 };
 27 //排序，从小到大
 28 bool cmp(node a,node b)
 29 {
 30     return a.cost<b.cost;
 31 }
 32 //存放边的信息
 33 vector<node> ve;
 34 
 35 //fa表示当前i的最远祖先
 36 int fa[110];
 37 //初始化fa，开始时自己是自己的祖先
 38 void init(int qwq)
 39 {
 40     for(int i=0;i<=qwq;i++)
 41     {
 42         fa[i]=i;
 43     }
 44 }
 45 //查找最远祖先，同时进行路径压缩
 46 int find(int x)
 47 {
 48     if(fa[x]==x)
 49     {
 50         return x;
 51     }
 52     return fa[x]=find(fa[x]);
 53 }
 54 //判断最远祖先是否相同
 55 bool che(int x,int y)
 56 {
 57     return find(x)==find(y);
 58 }
 59 //合并x,y，把他们放到同一个家族中
 60 void mer(int x,int y)
 61 {
 62     if(!che(x,y)) 
 63     {
 64         fa[fa[x]]=fa[y];
 65     }
 66     return ;
 67 }
 68 int n,m;
 69 //ma用于保存村庄之间的距离
 70 int ma[105][105];
 71 //bj用于标记已经连接的村庄编号
 72 int bj[105][105];
 73 int main()
 74 {
 75     scanf("%d",&n);
 76     //初始化
 77     init(n);
 78     for(int i=1;i<=n;i++)
 79     {
 80         for(int j=1;j<=n;j++)
 81         {
 82             scanf("%d",&m);
 83             ma[i][j]=m;
 84         }
 85     }
 86     int a,b;
 87     //初始化bj
 88     memset(bj,0,sizeof(bj));
 89     scanf("%d",&m);
 90     for(int i=0;i<m;i++)
 91     {
 92         scanf("%d %d",&a,&b);
 93         //标记，
 94         bj[a][b]=1;
 95         bj[b][a]=1;
 96     }
 97     node no;
 98     for(int i=2;i<=n;i++)
 99     {
100         for(int j=1;j<i;j++)
101         {
102             //当村庄之间没有道路时
103             if(bj[i][j]==0)
104             {
105                 no.u=i;
106                 no.v=j;
107                 no.cost=ma[i][j];
108                 ve.push_back(no);
109             }
110             else
111             {//当村庄之间有道路时，合并这两个村庄
112                 mer(i,j);
113             }
114         }
115     }
116     int ans=0;
117     //排序
118     sort(ve.begin(),ve.end(),cmp);
119     for(int i=0;i<ve.size();i++)
120     {
121         //当两个村庄之间没有连接时
122         if(!che(ve[i].u,ve[i].v))
123         {
124             //合并
125             mer(ve[i].u,ve[i].v);
126             ans+=ve[i].cost;
127         }
128     }
129     printf("%d\n",ans);
130     //清除容器内存
131     ve.clear();
132 }