克鲁斯卡尔算法的核心是对边贪心选取，前提是要先对边进行排序，当边的数量特别大的话依然会出问题，所以当图为稠密图的时候应该使用prim算法。 prim算法实质是迪杰斯特拉算法通过更新源点到各点的最小距离来得出最小的边权和。 POJ1789
#include <cstdio> #include <cstring> #define INF 1<<27 const int MAXN = 2019; char s[MAXN][17]; int m[MAXN][MAXN]; int low[MAXN], visited[MAXN]; int n; int Cont(int x, int y) { int c = 0; for(int i = 0; i < 7; i++) { if(s[x][i] != s[y][i]) c++; } return c; } int prim() { int i, j; int pos, minn, result = 0; memset(visited,0,sizeof(visited)); visited[0] = 1; pos = 0; for(i = 0; i < n; i++) { low[i] = m[pos][i]; } for(i = 0; i < n-1; i++) { minn = INF; pos = -1; for(j = 0; j < n; j++) { if(!visited[j] && low[j] < minn) { minn = low[j]; pos = j; } } result += minn; visited[pos] = 1; for(j = 0; j < n; j++) { if(!visited[j] && low[j]>m[pos][j]) low[j] = m[pos][j]; } } return result; } int main() { while(scanf("%d",&n) && n) { getchar(); for(int i = 0; i < n; i++) { gets(s[i]); } memset(m,0,sizeof(m)); for(int i = 0; i < n-1; i++) { for(int j = i+1; j < n; j++) { m[i][j] = m[j][i] = Cont(i,j); } } int ans = prim(); printf("The highest possible quality is 1/%d.\n",ans); } return 0; }