hdu1102

第一道最小生成树问题

 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #define maxn 10000+100
 6 using namespace std;
 7 int r[maxn];
 8 int u[maxn];
 9 int v[maxn];
10 int w[maxn];
11 int p[maxn];
12 int map[110][110];
13 bool inmap[110][110];
14 int cmp(const int i,const int j){return w[i]<w[j];}
15 int find(int x)
16 {
17     return p[x]==x?x:p[x]=find(p[x]);
18 }
19 void merge(int x,int y)
20 {
21     int a=find(x),b=find(y);
22     p[a]=b;
23 }
24 int main()
25 {
26     int cnt;
27     int n,q;
28     while(~scanf("%d",&n))
29     {
30         for(int i=1;i<=n;i++)
31             for(int j=1;j<=n;j++)
32             scanf("%d",&map[i][j]);
33         memset(inmap,0,sizeof(inmap));
34         scanf("%d",&q);
35         for(int i=1;i<=n;i++)
36         {
37             p[i]=i;
38         }
39         for(int i=1;i<=q;i++)
40         {
41             int u,v;
42             scanf("%d%d",&u,&v);
43             merge(u,v);
44             inmap[u][v]=inmap[v][u]=true;
45         }
46         int cnt=0;
47         for(int i=1;i<=n;i++)
48             for(int j=1;j<i;j++)//读取一半的图即可
49                 if(!inmap[i][j])
50                 {
51                     u[cnt]=i;
52                     v[cnt]=j;
53                     w[cnt++]=map[i][j];
54                 }
55         int ans=0;
56         for(int i=0;i<cnt;i++) r[i]=i;
57         //cout<<"cnt="<<cnt<<endl;
58         sort(r,r+cnt,cmp);
59         for(int i=0;i<cnt;i++)
60         {
61             int e=r[i];int x=find(u[e]);int y=find(v[e]);
62             if (x!=y)
63                 {ans+=w[e];merge(x,y);}
64         }
65         printf("%d
",ans);
66 
67     }
68     return 0;
69 }

View Code

题目是说：n个城市间修建道路使之联通，其中有些路已经修好，再添加几条道路，是城市间能联通，且路程最短......