POJ-1789 Truck History 최소 스패닝 트리

6081 단어 history

 
전체 자동차의 진화 과정에서 바뀌어야 할 가장 적은 문자 수를 계산하다.변경된 문자 수의 계산 방식은 1-7자리의 서로 다른 개수이다.
 
코드는 다음과 같습니다.
 
#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;



int N, pos, set[2005];



char s[2005][10];



struct Node

{

    int x, y, diff;

    bool operator < (Node t) const

    {

        return diff < t.diff;

    }

}e[4000005];



int diff(int x, int y)

{

    int cnt = 0;

    for (int i = 0; i < 7; ++i) {

        if (s[x][i] != s[y][i]) {

            ++cnt;

        }

    }

    return cnt;

}



int find(int x)

{

    return set[x] = x == set[x] ? x : find(set[x]);

}



void merge(int x, int y) 

{

    set[x] = y;

}



int main()

{

    int a, b, ans, cnt;

    while (scanf("%d", &N), N) {

        pos = ans = cnt = 0;

        for (int i = 1; i <= N; ++i) {

            scanf("%s", s[i]); 

            set[i] = i;

        }

        for (int i = 1; i <= N; ++i) {

            for (int j = i+1; j <= N; ++j) {      

                ++pos;

                e[pos].x = i, e[pos].y = j;

                e[pos].diff = diff(i, j);;

            }

        }

        sort(e+1, e+1+pos);

        for (int i = 1; i <= pos; ++i) {

            a = find(e[i].x), b = find(e[i].y);

            if (a != b) {

                printf("%d %d
", e[i].x, e[i].y); ++cnt; merge(a, b); ans += e[i].diff; if (cnt == N-1) { break; } } } printf("The highest possible quality is 1/%d.
", ans); } return 0; }

좋은 웹페이지 즐겨찾기