zoj2158.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <cstdio>
#include <cstring>

int N;
char Data[2000][7];
char dis[2000][2000];
char d[2000];
bool mk[2000];

void init (){
    int i , j , k ;
    for (i = 0; i < N; i++) scanf("%s", Data[i]);
    
    for (i = 0; i < N; i ++)
        for (j = i + 1; j < N; j ++) {
            dis[i][j] = 0;
            for (k = 0; k < 7; k ++)
                if (Data[i][k] != Data[j][k] ) dis[i][j] ++;
            dis[j][i] = dis[i][j];
        }
}

int Prim(){
    for (int i = 1; i < N; i++) d[i] = dis[0][i];
    memset(mk, 0, sizeof(mk));
    mk[0] = 1;
    
    int ret = 0;
    for (int i = 1; i < N; i++){
        int k = -1;
        for (int j = 1; j < N; j++) if (!mk[j])
            if (k == -1 || d[j] < d[k]) k = j;
        if (k == -1) break;
        mk[k] = 1;
        ret += d[k];      
        for (int j = 1; j < N; j++) if (!mk[j] && dis[k][j] < d[j])
            d[j] = dis[k][j];
    }
    return ret;
}

int main(){
    while (scanf("%d", &N), N){
        init();
        printf("The highest possible quality is 1/%d.\n", Prim());
    }
    return 0;
}