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 