克鲁斯卡算法)"/>
c语言镖局运输图的解法(克鲁斯卡算法)
7-1 镖局运镖 (23 分)
镖局的运镖,就是运货(类似现在的物流)。镖局每到一个新地方开展业务,都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低,不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线,已知城市的地图,你需要选择一些道路进行疏通,以便镖局可以到达任意一个城市,要求花费的银子越少越好。
输入格式:
第一行有两个数n和m,n表示有n个城市(编号从1到n),m表示有m条道路。接下来m行,每行形如“a b c”用来表示一条道路,意思是城市a到城市b连通且打点需要花费的银子数是c。
输出格式:
若通过打点能抵达所有城市,则输出最少需要花费的银子总数。若不能抵达所有的城市则输出“impossible”。
输入样例:
3 3
1 2 1
1 3 2
2 3 4
输出样例:
3
这道题 是 最小生成树算法的一个利用
由于这道题 是稀疏网形式的图 所以 我采用克鲁斯卡算法
#include<stdio.h>
#include<string.h>
int parent[1000];
//西柚小华伟
typedef struct Edge{int a;int b;int w;
}Edge;//这是记录图的操作 两边的他们的权值Edge edges[100];
int Find(int x)//这个是为了找到顶点的下标位置 如果不是为-1 则一直找到他的爹 就是他结点的终点
{while(parent[x]
更多推荐
c语言镖局运输图的解法(克鲁斯卡算法)
发布评论