农场--Kruskal应用--c++

【题目要求】

农场里有一些奶牛，作为食物的草料不够了。农场主需要去别的农场借草料。该地区有N (2 <= N <= 2,000) 个农场，农场名称用数字N标识，农场之间的道路是双向的，一共有M (1 <= M <= 10,000)条道路，单条长度不超过1,000,000,000里。有一些农场之间有多条道路相连。所有农场都有通路，连接到农场主的农场。农场主的农场是1号农场，他从自己的农场出发，去所有的农场借草料。

农场主需要在路上携带足够的水，假设马跑完一里路需要1盎司的水，在任意一个农场都可以补充水。那么他应该携带一个多大容量的水壶呢？

【思路】

求最小生成树，并找到生成树中的最长路径即为所求。

【输入输出】

输入：

第一行输入 N M

下面多行，每一行表示起点农场编号 终点农场编号 路径长度

输出：

水壶的容量，单位为盎司

【测试数据】

【样例输入】

3 3

1 2 12

2 3 123

1 3 50
【样例输出】

50

【代码--不用类】

#include<iostream>
#include<string>
using namespace std;
int arc[1000][1000];
int edgeNUM;  //边个数
int vertexNUM; //地点个数
//记录起始位置，终点位置，权值的结构体
struct Edge
{int from, to;int weight;
};//查找根节点
int findRoot(int parent[], int v)
{while (parent[v] != -1){v = parent[v];}return v;
}int main()
{cin >> vertexNUM >> edgeNUM;Edge e[1000];//输入for (int i = 0; i < edgeNUM; i++){cin >> e[i].from;cin >> e[i].to;cin >> e[i].weight;}//对权值进行排序Edge temp;for (int j = 0; j < edgeNUM - 1; j++){for (int i = 0; i < edgeNUM - 1 - j; i++){if (e[i].weight > e[i + 1].weight){temp = e[i];e[i] = e[i + 1];e[i + 1] = temp;}}}int parent[1000] ;  //记录根节点的数组//初始化for (int i = 0; i < vertexNUM; i++){parent[i] = -1;}int k = 0;int min[1000] = { 0 };for (int i = 0; i < edgeNUM; i++){if (i >= 1 && e[i - 1].from == e[i].from && e[i].to == e[i - 1].to){//筛选掉两地之间其他路径的情况，只考虑最短的那条路，因为前面已经对路径从小到大排了序，所以这里可以直接略过较长路径}else{int a = e[i].from;int b = e[i].to;//找到所在生成树的根节点int vex1 = findRoot(parent, a - 1); //因为题目下标是从1开始，而数组下标是从0开始，所以需要-1int vex2 = findRoot(parent, b - 1);//判断是否成环，如果两个节点的根节点下标不相等，不成环if (vex1 != vex2){   //合并生成树parent[vex2] = vex1;min[k] = e[i].weight;  //记录权值k++;}}}//遍历min找到最小生成树中的最长距离，即为农夫要带的水壶最大容量int MIN = min[0];for (int i = 0; i < k; i++){if (MIN < min[i]){MIN = min[i];}}cout << MIN;return 0;
}