1003 電話連線，1003連線
題目描述 Description
一個國家有n個城市。若干個城市之間有電話線連接，現在要增加m條電話線（電話線當然是雙向的了），使得任意兩個城市之間都直接或間接經過其他城市有電話線連接，你的程序應該能夠找出最小費用及其一種連接方案。
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 struct node
7 {
8 int u;
9 int v;
10 int w;
11 }edge[10001];
12 struct ans
13 {
14 int x;
15 int y;
16 }a[10001];
17 int num=1;
18 int f[1001];
19 int cmp(const node &a,const node &b)
20 {
21 return a.w<b.w;
22 }
23 int find(int x)
24 {
25 if(x!=f[x])
26 f[x]=find(f[x]);
27 return f[x];
28 }
29 void unionn(int x,int y)
30 {
31 int fx=find(x);
32 int fy=find(y);
33 f[fx]=fy;
34 }
35 int comp(const ans &a,const ans &b)
36 {
37 if(a.y>b.y)return 1;
38 if(a.y==b.y&&a.x<b.x)return 1;
39 return 0;
40 }
41 int now=1;
42 int main()
43 {
44 int n;
45 scanf("%d",&n);
46 for(int i=1;i<=n;i++)f[i]=i;
47 for(int i=1;i<=n;i++)
48 {
49 for(int j=1;j<=n;j++)
50 {
51 int p;
52 scanf("%d",&p);
53 if(j>i)
54 {
55 edge[num].u=i;
56 edge[num].v=j;
57 edge[num].w=p;
58 num++;
59 }
60 }
61 }
62 sort(edge+1,edge+num,cmp);
63 int k=0;
64 int tot=0;
65 int feiyong=0;
66 for(int i=1;i<=num;i++)
67 {
68 if(find(edge[i].u)!=find(edge[i].v))
69 {
70 unionn(edge[i].u,edge[i].v);
71 //printf("%d %d\n",edge[i].u,edge[i].v);
72 if(edge[i].w!=0)
73 {
74 tot++;
75 feiyong=feiyong+edge[i].w;
76 //ans1[now]=edge[i].u;
77 //ans2[now]=edge[i].v;
78 a[now].x=min(edge[i].u,edge[i].v);
79 a[now].y=max(edge[i].u,edge[i].v);
80 k++;
81 now++;
82 }
83
84 }
85 if(k==n-1)break;
86 }
87 /*for(int i=1;i<=now;i++)
88 {
89 for(int j=i;j<=now;j++)
90 {
91 if(ans1[j]>ans1[j+1])
92 {
93 swap(ans1[j],ans1[j+1]);
94 swap(ans1[j],ans2[j+1]);
95 }
96 }
97 }*/
98 sort(a+1,a+now,comp);
99 printf("%d\n",tot);
100 for(int i=1;i<=now-1;i++)
101 {
102 printf("%d %d\n",a[i].x,a[i].y);
103 }
104 printf("%d",feiyong);
105 return 0;
106 }
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 const int MAXN = 105;
5 const int INF = 2147483647;
6 int i, j, n;
7 long long ans = 0;
8 int edge[MAXN][MAXN], key[MAXN], p[MAXN], vis[MAXN] = {0}, //edge表示存的邊 key表示權值，p表示父親，vis表示是否已經存在已生成的樹中
9 f[MAXN], l[MAXN], m = 0; //f表示頭，右邊表示尾
10 int main() {
11 cin >> n;
12 for(i = 1; i <= n; i++)for(j = 1; j <= n; j++) cin >> edge[i][j];
13 for(i = 1; i <= n; i++) key[i] = INF;
14 key[1] = 0; //
15 p[1] = 1;
16 int Mini, Min;
17 for(i = 0; i < n; i++) { //之需要加最多n條邊，故循環n次
18 Min = INF;
19 for(j = 1; j <= n; j++) if(!vis[j] && key[j] < Min) {
20 Mini = j; //找key值最小的點，即與樹相鄰的節點的最小權值邊
21 Min = key[j];
22 }
23 vis[Mini] = 1; //設置訪問過，即生成樹已連接Mini這個節點
24 ans += key[Mini];
25 if(key[Mini]) {
26 f[m] = min(p[Mini], Mini); //字典序的邊
27 l[m++] = max(p[Mini], Mini); //同上
28 }
29 for(j = 1; j <= n; j++) //偽松弛，更新樹臨邊節點的key值並維護p域
30 if(!vis[j] && edge[Mini][j] < key[j]) {
31 key[j] = edge[Mini][j];
32 p[j] = Mini;
33 }
34 }
35 cout << m << endl;
36 for(i = 0; i < m; i++) cout << f[i] << ' ' << l[i] << endl;
37 cout << ans;
38 return 0;
39 }
