1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include
#include
#define MAX 500
/* 定义边(x,y)，权为w */
typedef struct
{
int x, y;
int w;
}edge;
edge e[MAX * MAX / 2];
/* father[x]表示x的父节点 */
int father[MAX];
int max;
/* 比较函数，按权值非降序排序 */
int cmp(const void *a, const void *b)
{
return (*(edge *)a).w - (*(edge *)b).w;
}
/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
}
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
/* 合并x,y所在的集合 */
void Union(int x, int y, int w)
{
if (x == y) return;
father[y] = x;
if (w > max) max = w;
}
int main()
{
int i, j, n, k, t;
int tmp;
scanf("%d", &t);
while (t--)
{
k = 0;
max = 0;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
Make_Set(i);
for (j = 0; j < n; j++)
{
/* 只读取上三角 */
if (i < j)
{
e[k].x = i;
e[k].y = j;
scanf("%d", &e[k].w);
k++;
}
else
{
scanf("%d", &tmp);
}
}
}
qsort(e, k, sizeof(edge), cmp);
for (i = 0; i < k; i++)
{
Union(Find_Set(e[i].x), Find_Set(e[i].y), e[i].w);
}
printf("%d\n", max);
}
//system("pause");
return 0;
}
#include
#include
#define MAX 100
/* 定义边(x,y)，权为w */
typedef struct
{
int x, y;
int w;
}edge;
edge e[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* father[x]表示x的父节点 */
int father[MAX];
int sum;
/* 比较函数，按权值(相同则按x坐标)非降序排序 */
int cmp(const void *a, const void *b)
{
if ((*(edge *)a).w == (*(edge *)b).w)
{
return (*(edge *)a).x - (*(edge *)b).x;
}
return (*(edge *)a).w - (*(edge *)b).w;
}
/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
/* 合并x,y所在的集合 */
void Union(int x, int y, int w)
{
if (x == y) return;
/* 将秩较小的树连接到秩较大的树后 */
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
sum += w;
}
/* 主函数 */
int main()
{
int i, n;
int x, y;
char chx, chy;
/* 读取边的数目 */
scanf("%d", &n);
getchar();
/* 读取边信息并初始化集合 */
for (i = 0; i < n; i++)
{
scanf("%c %c %d", &chx, &chy, &e[i].w);
getchar();
e[i].x = chx - 'A';
e[i].y = chy - 'A';
Make_Set(i);
}
/* 将边排序 */
qsort(e, n, sizeof(edge), cmp);
sum = 0;
for (i = 0; i < n; i++)
{
x = Find_Set(e[i].x);
y = Find_Set(e[i].y);
if (x != y)
{
printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);
Union(x, y, e[i].w);
}
}
printf("Total:%d\n", sum);
//system("pause");
return 0;
}
|
