- #define _CRT_SECURE_NO_WARNINGS
- #include<stdio.h>
- typedef struct Edge
- {
- int v1, v2;
- int wight;
- }Edge;
- int main()
- {
- int n, m;//結點數和邊數
- int i, j, k = 0;
- int count = 0;
- Edge edge[100];//邊集
- int vest[30];//判斷是否成環的編號數組
- scanf("%d %d", &n, &m);
- for (i = 0; i < m; i++)
- {
- scanf("%d %d %d", &edge[i].v1, &edge[i].v2, &edge[i].wight);
- if(edge[i].v1 > edge[i].v2)
- {
- int t = edge[i].v1;
- edge[i].v1 = edge[i].v2;
- edge[i].v2 = t;
- }
- }
- for (i = 1; i <= n; i++)//初始化編號數組
- vest[i] = i;
- for (i = 0; i < m - 1; i++)//排序
- {
- for (j = 0; j < m - i - 1; j++)
- {
- if (edge[j].wight > edge[j + 1].wight)
- {
- Edge t = edge[j];
- edge[j] = edge[j + 1];
- edge[j + 1] = t;
- }
- }
- }
- for (i = 0; i < m && count < n - 1; i++)
- {
- if (vest[edge[i].v1] != vest[edge[i].v2])//說明不構成環,打印
- {
- printf("%d %d %d\n", edge[i].v1, edge[i].v2, edge[i].wight);
- count++;
- int flag1 = vest[edge[i].v1];
- int flag2 = vest[edge[i].v2];
- for (j = 1; j <= n; j++)
- {
- if (vest[j] == flag2)//把全部編號為flag2的結點改為flag1
- vest[j] = flag1;
- }
- }
- }
- return 0;
- }
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
