#include <iostream> #include <cstdio> #include <algorithm> using namespace std; /** * 元素个数最大值 */ #define MAX_NUM 100 /** * 父亲节点,存储了每个"节点的父亲节点"的下标索引 */ int father[MAX_NUM]; /** * 树高度;当节点为根节点时,才记录该树的高度 */ int height[MAX_NUM]; /** * 带权边的定义 */ struct Edge { int from; //边的起点. int to; //边的终点. int length; //边的权值. /* * 重写小于号"<" */ bool operator<(const Edge &edge) const { return length < edge.length; } }; /** * 边集合 */ Edge edge[MAX_NUM * MAX_NUM]; /** * 初始化并查集的每个集合 */ void Init(int n) { /** * 题目已说明:城镇编号从1到N编号。 * 最初时,每个元素为一个单独的集合 */ for (int i = 1; i <= n; ++i) { /* * 每个节点就是一棵树,所以节点的父节点下标索引为其本身. * 注:初始化时"节点的父节点下标索引为其本身"为自定义,有些教材为-1. */ father[i] = i; //树高为1. height[i] = 1; } } /** * 优化--路径压缩 * 查找x节点的祖先,即x节点所在树的根节点 * @param x x节点 * @return x节点所在树的根节点 */ int Find(int x) { if (x != father[x]) { //不是根节点,递归向上查找. //执行完Find操作之后,都会将节点的父节点索引设置为根节点,实现"路径压缩"的效果. father[x] = Find(father[x]); } //当x节点的父节点索引为其本身时时,此时x节点即为根节点. return father[x]; } /** * 优化--大树并小树 * 合并x节点和y节点所在的两个集合 * @param x x节点 * @param y y节点 */ void Union(int x, int y) { /** * 合并两棵树 * 1、找到y节点的祖先 * 2、找到x节点的祖先 * 3、y节点的祖先的父节点 设置为 x节点的祖先,实现y所在集合并到x所在集合下 */ x = Find(x); y = Find(y); /* * 不为同一个集合 * 矮树作为高树的子树 */ if (x != y) { if (height[x] < height[y]) { //x树低于y树,则将y树作为x树的子树. father[x] = y; } else if (height[y] < height[x]) { father[y] = x; } else { //两棵树高度一样,合并后记得将树高+1. father[y] = x; height[x]++; } } } /** * Kruskal算法求最小生成树 * @param n 顶点数量 * @param edgeNum 边的数量 * @return 最小生成树的权值 */ int kruskal(int n, int edgeNum) { // Init(n); //按边的权值从高到低进行排序(Kruskal主要的性能消耗). sort(edge, edge + edgeNum); /* * !!!求累加时,一定要将变量初始化为0!!! * !!!求累乘时,一定要将变量初始化为1!!! */ int sumWeight = 0; //遍历所有边. for (int i = 0; i < edgeNum; ++i) { //当前节点. Edge curEdge = edge[i]; int fromRoot = Find(curEdge.from); int toRoot = Find(curEdge.to); /* * 判断是否为同一个集合 * 若不是,则将集合合并 */ if (fromRoot != toRoot) { Union(curEdge.from, curEdge.to); //权值累加. sumWeight += curEdge.length; } } return sumWeight; } /** * 继续畅通工程--浙江大学 * @return */ int main() { int n; while (cin >> n) { if (n == 0) { break; } Init(n); //计算边数. int edgeNum = n * (n - 1) / 2; for (int i = 0; i < edgeNum; ++i) { int status; cin >> edge[i].from >> edge[i].to >> edge[i].length >> status; if (status == 1) { /* * 对于修建好的道路,我们先将其连接的顶点进行合并 */ Union(edge[i].from, edge[i].to); } } int ans = kruskal(n, edgeNum); cout << ans << endl; } return 0; }