//土尔逊Torson 编写于2023/07/05 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 100; struct Edge13501 { int from; //边的起点 int to; //边的终点 int length; //边的长度 bool operator<(const Edge13501& e) const { return length < e.length; } }; Edge13501 edge13501[MAXN * MAXN]; //边集 int father13501[MAXN]; //父亲结点 int height13501[MAXN]; //结点高度 void Initial13501(int n) { //初始化 for (int i = 0; i <= n; i++) { father13501[i] = i; height13501[i] = 0; } } int Find13501(int x) { //查找根结点 if (x != father13501[x]) { father13501[x] = Find13501(father13501[x]); } return father13501[x]; } void Union13501(int x, int y) { //合并集合 x = Find13501(x); y = Find13501(y); if (x != y) { if (height13501[x] < height13501[y]) { father13501[x] = y; } else if (height13501[y] < height13501[x]) { father13501[y] = x; } else { father13501[y] = x; height13501[x]++; } } return; } int Kruskal13501(int n, int edgeNumber) { Initial13501(n); sort(edge13501, edge13501 + edgeNumber); //按权值排序 int sum = 0; for (int i = 0; i < edgeNumber; ++i) { Edge13501 current = edge13501[i]; if (Find13501(current.from) != Find13501(current.to)) { Union13501(current.from, current.to); sum += current.length; } } return sum; } int main() { int n; while (scanf("%d", &n) != EOF) { if (n == 0) { break; } int edgeNumber = n*(n - 1) / 2; for (int i = 0; i < edgeNumber; ++i) { int status; scanf("%d%d%d%d", &edge13501[i].from, &edge13501[i].to, &edge13501[i].length, &status); if (status == 1) { edge13501[i].length = 0; } } int answer = Kruskal13501(n, edgeNumber); printf("%d\n", answer); } system("pause"); return EXIT_SUCCESS; } // 64 位输出请用 printf("%lld")