poj1789(prim)

prim和kruskal都是求解最小生成树的算法。这道题题意就是有N个字符串就是N个节点，而字符串之间的距离就是节点边的长度，求其最小生成树的边权和。

由于是第一次用prim，所以在求安全边的时候采用的是暴力的方法，所以我这个算法是O(n^2)的，跑了近1500ms，吓出一身冷汗……如果采用优先队列或者堆等数据结构应该会快，但是代码也会相应复杂了。

#include <iostream>

#include <string>

using namespace std;

int n;

string str[];

int dis[][];

int key[];

bool visited[];

const int LEN = ;

int calDis(string str1, string str2)

{

    int ans = ;

    for (int i = ; i < LEN; i++){

        if (str1[i] != str2[i]){

            ans++;

        }

    }

    return ans;

}

int prime()

{

    int sum = ;

    visited[] = true;

    for (int i = ; i < n; i++){

        key[i] = dis[][i];

    }

    for (int i = ; i < n; i++){

        int min = ;

        int index = ;

        for (int j = ; j < n; j++){

            if (!visited[j] && key[j] < min){

                index = j;

                min = key[j];

            }

        }

        visited[index] = true;

        sum += key[index];

        for (int j = ; j < n; j++){

            if (!visited[j] && dis[index][j] < key[j]){

                key[j] = dis[index][j];

            }

        }

    }

    return sum;

}

int main()

{

    while (cin >> n && n){

        memset(dis, , sizeof(dis));

        memset(key, , sizeof(key));

        memset(visited, , sizeof(visited));

        for (int i = ; i < n; i++){

            cin >> str[i];

        }

        for (int i = ; i < n; i++){

            for (int j = i; j < n; j++){

                int tmpDis = calDis(str[i], str[j]);

                dis[i][j] = tmpDis;

                dis[j][i] = tmpDis;

            }

        }

        cout << "The highest possible quality is 1/" << prime() << '.' << endl;

    }

    return ;

}

巴特西

poj1789(prim)

最新文章

热门文章