POj 1789

• 重点在建图,每个字符串是一个顶点,权值是字符串每个位置字符不同的个数,
• 每两个字符串之间的边权值相同,方向相反,所以不需要完全2层循环建图.

  for (int i=1; i<=n; i++) 
  			for (int j=i; j<=n; j++) {
  				a[i][j] = a[j][i] = countnum(ch[i],ch[j]);
  //				printf("%s  %s a[][] = %d\n",ch[i],ch[j],a[i][j]);
  			}

• 由于边多,prime算法合适,

  #include <iostream>
  #include <string.h>
  #define INF 0x3f3f3f3f
  using namespace std;
  const int maxn = 2010;
  
  int a[maxn][maxn];
  char ch[maxn][8];
  bool vis[maxn];
  int dist[maxn];
  int n;
  void prim() {
  	memset(vis, 0 ,sizeof vis);
  	vis[1] = 1; //随便找一个点加入最小生成树中
  	for (int i=1; i<=n; i++) dist[i] = a[1][i]; // 更新每个点到树的距离
  
  	long sum = 0;//最短的路径长度
  	for (int i=1; i<n; i++) { // 开始找n-1条边
  		long minn = INF; // 距离树最短的边
  		int point = INF; // 距离树最近的点
  		for (int i=1; i<=n; i++) {
  			if (!vis[i] && dist[i]<minn ) {
  				point = i;
  				minn = dist[i];
  			}
  		}
  		vis[point] = true; // 该点访问过（在树中）
  		sum += dist[point];
  
  		//通过刚刚入树的点   更新所有没有访问过的点到新的最小生成树的距离
  		for (int i=1; i<=n; i++) {
  			if ( !vis[i] && a[point][i]<dist[i] )
  				dist[i] = a[point][i];
  		}
  	}
  	printf("The highest possible quality is 1/%d.\n",sum);
  }
  int countnum(char* a,char* b) {
  	int cnt = 0;
  	for (int i=0; i<7; i++) 
  		if (a[i] != b[i]) 
  			cnt++;
  	return cnt;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	while (scanf("%d",&n) && n) {
  		memset(a,0x3f,sizeof a);
  		for (int i=1; i<=n; i++) scanf("%s",ch[i]);
  
  		for (int i=1; i<=n; i++) 
  			for (int j=i; j<=n; j++) {
  				a[i][j] = a[j][i] = countnum(ch[i],ch[j]);
  //				printf("%s  %s a[][] = %d\n",ch[i],ch[j],a[i][j]);
  			}
  		prim();
  	}
  	return 0;
  }