int g[MAXN][MAXN]; int w[MAXN]; // w[i] 已选定集合中所有点到 i 的直接连边边权总和 int fa[MAXN]; // 处理合并操作后,删掉其中一个点 bool ins[MAXN];
intmain(){ int n, m; while (cin >> n >> m) { memset(g, 0, sizeof g); for (int i = 1; i <= m; i++) { int u = read(); int v = read(); int c = read(); g[u][v] += c; g[v][u] += c; } for (int i = 0; i < n; i++) { fa[i] = i; } int ans = INF; int remain = n; while (remain > 1) { memset(w, 0, sizeof w); memset(ins, false, sizeof ins); ins[0] = true; int u = 0; int v = 0; for (int i = 1; i < remain; i++) { u = v; v = -1; int cut_v = -1; for (int j = 1; j < remain; j++) { if (!ins[j]) { w[j] += g[fa[j]][fa[u]]; if (w[j] > cut_v) { cut_v = w[j]; v = j; } } } ins[v] = true; } ans = min(ans, w[v]);
// 类似并查集的合并操作 for (int i = 1; i < remain; i++) { if (i == v) continue; g[fa[i]][fa[0]] += g[fa[i]][fa[v]]; g[fa[0]][fa[i]] += g[fa[v]][fa[i]]; } remain--; fa[v] = fa[remain]; // 相当于是把 v 删掉了 }