记录端点数与顶点(村庄)数是否相同,如果相同,所形成的最短路径为最优解输出
#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define MAX 5000 // 顶点 权 排序 树(并查集) int u[MAX], v[MAX], w[MAX], r[MAX], p[105], sum, num, n, nc; int cmp(const int a, const int b) { return w[a]<w[b]; } int find(int x) { return p[x]==x?x:find(p[x]); } bool Kruskal() { int i; for (i=1; i<=num; i++) p[i] = i; for (i=1; i<=n; i++) r[i] = i; sort(r+1, r+n+1, cmp); for (i=1; i<=n; i++) { int t = r[i]; int x = find(u[t]); int y = find(v[t]); if (x!=y) { sum += w[t]; p[x] = y; nc++; //记录端点数 } } if (nc==n-1) //端点数=顶点数 返回真 return true; else return false; } int main() { int i; while (cin>>num>>n && num) { for (i=1; i<=num; i++) scanf("%d%d%d", &u[i], &v[i], &w[i]); nc = 0; sum = 0; if (Kruskal()) printf("%d\n", sum); else printf("?\n"); } return 0; }