要求图的最小生成树的长度之和，边集表示已找到的最小距离的边
初始d数组，表示点到此边集的最小距离，如果d[i]==0，则说明i点在边集中
dis二维数组，表示两点间的距离
初始时，d[i]表示i点到0点距离，d[0]=1
找出d[i]中的最小值d[min]，把min点加入边集，对于除了边集中的所有点j，如果j到min的距离比d[j]小，则d[j]=dis[j][min]，（原d[j]为到0点的距离，这样d[j]永远都是到边集的最小距离）
#include <iostream> #define MAX 2001 char types[MAX][8]; char dis[MAX][MAX]; char d[MAX]; #define INF 127 int prim(int n){ int i,j,k,ti; int mindis,total=0; d[0]=0; for(i=1;i<n;i++) d[i]=dis[i][0]; for(i=1;i<n;i++){ mindis=INF; //找到最小权值 for(k=0;k<n;k++) { if(d[k]&&d[k]<mindis){ ti = k; mindis = d[k]; } } total+=mindis; d[ti]=0; for(j=0;j<n;j++){ if(d[j]&&dis[j][ti]<d[j])d[j]=dis[j][ti]; } } return total; } int main(int argc, char* argv[]) { //freopen("i://t.txt","r",stdin); int c,i,j,k; while(scanf("%d",&c)&&c){ for(i=0;i<c;i++) { scanf("%s",types[i]); for(j=0;j<i;j++){ int dif = 0; for(k=0;k<7;k++) if(types[j][k]!=types[i][k])dif++; dis[i][j] = dis[j][i] = dif; } } printf("The highest possible quality is 1/%d.\n",prim(c)); } return 0; }