【kruscal】【最小生成树】bzoj2421 Constructing Roads

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int rank[10001],fa[10001],n,m,a[101][101],q,x,y,f1,f2,ans;
 6 void init(){for(int i=1;i<=n;i++) fa[i]=i;}
 7 int findroot(int x) 
 8 {
 9     if(fa[x]==x) return x;
10     int rt=findroot(fa[x]);
11     fa[x]=rt;
12     return rt;
13 }
14 void Union(int U,int V)
15 {
16     if(rank[U]<rank[V]) fa[U]=V;
17     else
18       {
19         fa[V]=U;
20         if(rank[U]==rank[V]) rank[U]++;
21       }
22 }
23 struct Edge{int u,v,w;Edge(const int &a,const int &b,const int &c){u=a;v=b;w=c;}Edge(){}};
24 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}
25 Edge edges[10001];
26 int main()
27 {
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++)
30       for(int j=1;j<=n;j++)
31         scanf("%d",&a[i][j]);
32     for(int i=1;i<=n;i++)
33       for(int j=i+1;j<=n;j++)
34         edges[++m]=Edge(i,j,a[i][j]);
35     sort(edges+1,edges+m+1,cmp);
36     scanf("%d",&q);
37     init();
38     for(int i=1;i<=q;i++)
39       {
40           scanf("%d%d",&x,&y);
41           f1=findroot(x); f2=findroot(y);
42           if(f1!=f2) Union(f1,f2);
43       }
44     for(int i=1;i<=m;i++)
45       {
46           f1=findroot(edges[i].u); f2=findroot(edges[i].v);
47           if(f1!=f2)
48           {
49               Union(f1,f2);
50               ans+=edges[i].w;
51           }
52       }
53     printf("%d\n",ans);
54     return 0;
55 }