1. 题目列表

• POJ1789（prim算法）
• POJ2485（prim）
• POJ1258（prim）
• POJ3026（BFS+prim）

2. POJ1789——Truck History

2.1 题目描述

Description

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of company's history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on.

Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan -- i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as
1/Σ(to,td)d(to,td)

where the sum goes over all pairs of types in the derivation plan such that to is the original type and td the type derived from it and d(to,td) is the distance of the types.
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan.
Input

The input consists of several test cases. Each test case begins with a line containing the number of truck types, N, 2 <= N <= 2 000. Each of the following N lines of input contains one truck type code (a string of seven lowercase letters). You may assume that the codes uniquely describe the trucks, i.e., no two of these N lines are the same. The input is terminated with zero at the place of number of truck types.
Output

For each test case, your program should output the text "The highest possible quality is 1/Q.", where 1/Q is the quality of the best derivation plan.

Sample Input

4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0
Sample Output

The highest possible quality is 1/3.

2.2 解决思路

题意：有n个车子，每个车子有个代码，定义任意两个车子i和j的距离为不同代码的个数，
    并且除了第一辆车，其他车都是由某辆车的代码演化而来，求最小的演化距离。
    
本题即以第一辆车为源点，求最小生成树的路径和。在算法的选择上，由于每一辆车和其他车都会有连接边，
所以是稠密图，选择prim算法。若顶点多，边少，选用克鲁斯卡尔算法。


使用邻接表存储会超内存。。可能维护vector结构所需要的内存过大？ 
使用邻接矩阵不会。。 

2.3 代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

/*
    题意：有n个车子，每个车子有个代码，定义任意两个车子i和j的距离为不同代码的个数，
        并且除了第一辆车，其他车都是由某辆车的代码演化而来，求最小的演化距离。
        
    本题即以第一辆车为源点，求最小生成树的路径和。
    
    使用邻接表存储会超内存。。可能维护vector结构所需要的内存过大？ 
    使用邻接矩阵不会。。 
*/
const int maxn = 2001;
const int INF = 1e7;
int g[maxn][maxn];
int d[maxn];
bool visited[maxn];
char code[maxn][8];

int getDist(char c1[], char c2[], int len){
    int sum = 0;
    for (int i = 0; i < len; i++)
        if (c1[i] != c2[i])
            sum++;
    return sum;
}

int Prim(int n){
    int sum = 0;
    fill(visited, visited + maxn, false);
    fill(d, d + maxn, INF);
    d[1] = 0;
    for (int i = 1; i <= n; i++){
        int u = -1, MIN = INF;
        for (int j = 1; j <= n; j++){
            if (!visited[j] && d[j] < MIN){
                MIN = d[j];
                u = j;
            }
        }
        if (u == -1) break;
        sum += MIN;
        visited[u] = true;
        for (int v = 1; v <= n; v++){
            if (g[u][v] != INF && g[u][v] < d[v])
                d[v] = g[u][v];
        }
    }
    return sum;
}

int main(){
    int n;
    while (~scanf("%d", &n) && n){
        fill(g[0], g[0] + maxn * maxn, INF);
        for (int i = 1; i <= n; i++){
            scanf("%s", code[i]);
            // 计算 1~ i - 1号节点与其的距离 
            for (int j = 1; j < i; j++){
                if (i == j) continue;
                int dist = getDist(code[i], code[j], 7);
                g[i][j] = g[j][i] = dist;
            }
        }
        int res = Prim(n);
        printf("The highest possible quality is 1/%d.\n", res);
    }
    return 0;
}

3. POJ3026——Borg Maze

3.1 题目描述

Description

The Borg is an immensely powerful race of enhanced humanoids from the delta quadrant of the galaxy. The Borg collective is the term used to describe the group consciousness of the Borg civilization. Each Borg individual is linked to the collective by a sophisticated subspace network that insures each member is given constant supervision and guidance.

Your task is to help the Borg (yes, really) by developing a program which helps the Borg to estimate the minimal cost of scanning a maze for the assimilation of aliens hiding in the maze, by moving in north, west, east, and south steps. The tricky thing is that the beginning of the search is conducted by a large group of over 100 individuals. Whenever an alien is assimilated, or at the beginning of the search, the group may split in two or more groups (but their consciousness is still collective.). The cost of searching a maze is definied as the total distance covered by all the groups involved in the search together. That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3.
Input

On the first line of input there is one integer, N <= 50, giving the number of test cases in the input. Each test case starts with a line containg two integers x, y such that 1 <= x,y <= 50. After this, y lines follow, each which x characters. For each character, a space '' stands for an open space, a hash mark#'' stands for an obstructing wall, the capital letter A'' stand for an alien, and the capital letterS'' stands for the start of the search. The perimeter of the maze is always closed, i.e., there is no way to get out from the coordinate of the ``S''. At most 100 aliens are present in the maze, and everyone is reachable.
Output

For every test case, output one line containing the minimal cost of a succesful search of the maze leaving no aliens alive.

Sample Input

2
6 5
##### 
#A#A##
# # A#
#S  ##
##### 
7 7
#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
#####  
Sample Output

8
11

3.2 解决思路

BFS+Prim

• 首先使用BFS求A或S任意两个点间的最短距离，并使用该距离建图。
• 使用Prim算法求解最小生成树，经过分析可知，答案就是最小生成树路径和。

此题应注意几个坑点：

• 1. 读入含空格的字符数组时，使用gets(char*[])或scanf("%c)，不能使用scanf("%s)，它是以空格为分界符。
• 2. 使用getchar()或gets来过滤字符数组之前的换行符，因为换行符仍然保留在输入缓冲区，需要过滤掉
• 3. 注意本题的建图方法：给节点标上序号。
• 4. 此题的节点数较少，应选择适合于稀疏图的最小生成树算法Prim算法。
• 5. 合理的初始化变量。

3.3 代码

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

struct Node{
    int x, y;
    int step;
};
const int maxn = 110;
const int INF = 1e6;
int g[maxn][maxn], d[maxn], xmax, ymax, hashtable[55][55];
bool visited[maxn], vis[55][55];
char map[55][55];
int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, -1, 1};

// 广搜，计算所有节点的最短距离 
void BFS(Node s){
    memset(vis, false, sizeof(vis));
    int sx = s.x, sy = s.y, step = s.step;
    queue<Node> q;
    q.push(s);
    while (!q.empty()){
        Node node = q.front();
        int x = node.x, y = node.y, step = node.step;
        q.pop();
        if (map[x][y] == 'A' || map[x][y] == 'S'){
            g[hashtable[x][y]][hashtable[sx][sy]] = node.step;
        }
        vis[node.x][node.y] = true;
        for (int i = 0; i < 4; i++){
            int newX = x + X[i];
            int newY = y + Y[i];
            if (!(newX < 0 || newX >= xmax || newY < 0 || newY >= ymax || 
            vis[newX][newY] || map[newX][newY] == '#'
            )){
                Node newNode;
                newNode.x = newX, newNode.y = newY, newNode.step = step + 1;
                q.push(newNode);
            }
        } 
    }
}

int Prim(int s, int n){
    int sum = 0;
    fill(visited, visited + maxn, false);
    fill(d, d + maxn, INF);
    d[s] = 0;
    for (int i = 1; i <= n; i++){
        int u = -1, MIN = INF;
        for (int j = 1; j <= n; j++){
            if (!visited[j] && d[j] < MIN){
                MIN = d[j];
                u = j;
            }
        }
        if (u == -1) break;
        sum += MIN;
        visited[u] = true;
        for (int v = 1; v <= n; v++){
            if (g[u][v] != INF && g[u][v] < d[v])
                d[v] = g[u][v];
        }
    }
    return sum;
}

void output(){
    for (int i = 0; i < xmax; i++){
        printf("%s\n", map[i]);
    }
}

int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        fill(g[0], g[0] + maxn * maxn, INF);
        int n = 1, s;
        scanf("%d%d", &ymax, &xmax);
        gets(map[0]);
        for (int i = 0; i < xmax; i++){
            gets(map[i]);
            for (int j = 0; j < ymax; j++){
                if (map[i][j] == 'S' || map[i][j] == 'A'){
                    // 给节点A或S标号，并记录位置坐标 
                    hashtable[i][j] = n++;
                }
            }
        }
        // 广搜计算各个点之间最小的距离   
        for (int i = 0; i < xmax; i++)
            for (int j = 0; j < ymax; j++){
                if (map[i][j] == 'A' || map[i][j] == 'S'){
                    Node node;
                    node.x = i, node.y = j, node.step = 0;
                    BFS(node);
                }
            } 
        int res = Prim(1, n - 1); // 顶点编号1~n，从任意一个节点开始  
        printf("%d\n", res);
    }
    return 0;
} 

4. 总结

最小生成树问题往往是一个贪心问题，求最小值或最大值，求的是在保证图连通的情况下最小代价。此类题目，应快速准确把握题意，使用Prim或克鲁斯卡尔算法求解。

• Prim算法可类比Djkstra算法，适用于边密集图，使用邻接矩阵的时间复杂度为，邻接表为
• 克鲁斯卡尔算法使用并查集实现，适用于边稀疏图，时间复杂度为。

记住两种算法的模板