[HOJ]1632、[POJ]1251 Jungle Roads

这道题是图的应用，通过对数据结构的学习，我发现现在就是图的部分掌握的还不是很好，包括图的搜索，最小生成树，最短路径以及拓扑排序等应用缺乏实际的操作和解题的经验，老师跟我们说过对数据结构要熟悉到像背乘法口诀一样，能过信手拈来的程度，所以这也是我应该加强的部分吧，总之，多做题，多熟悉一些经典的算法，并且掌握它，这是对我最基本的要求也是应该去做的

对于这个题要求的就是图的最小生成树，总共有两个比较好的算法，那就是prim算法和克鲁斯卡尔算法，之前对它们的了解仅仅在于课堂上老师的讲解，而没有实际的操作，所以这次遇到这个题的时候才发现自己虽然理解了算法的思想但是对于算法的实现还是欠缺很多细节方面的考虑，所以要谨记一点：对于算法，你看十遍还不如动手实现一边，通过自己的一步一步的调试才能发现自己到底对这个算法是否了解的很好，才能在以后应用到它！

下面是用克鲁斯卡尔算法实现的这道题，之后还是会尝试用prim算法解决它

题目：Jungle Roads

：

Input

Output

Sample Input

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

Sample Output

216
30

2
A 1 B 99
3
A 2 B 99 C 99
B 1 C 99
16
A 3 B 7 C 12 P 2
B 14 C 11 D 6 E 1 F 33 G 44 H 5 I 9 J 12 K 3 L 10 M 35 N 66 O 13 P 17
C 1 D 8
D 1 E 1
E 1 F 99
F 1 G 77
G 1 H 5
H 1 I 66
I 1 J 7
J 1 K 44
K 1 L 99
L 1 M 14
M 1 N 8
N 1 O 33
O 1 P 9
16
A 15 B 1 C 1 D 1 E 1 F 1 G 1 H 1 I 1 J 1 K 1 L 1 M 1 N 1 O 1 P 1
B 0
C 0
D 0
E 0
F 0
G 0
H 0
I 0
J 0
K 0
L 0
M 0
N 0
O 0
16
A 1 P 1
B 1 P 1
C 1 P 1
D 1 P 1
E 1 P 1
F 1 P 1
G 1 P 1
H 1 P 1
I 1 P 1
J 1 P 1
K 1 P 1
L 1 P 1
M 1 P 1
N 1 P 1
O 1 P 1
26
A 1 B 1
B 1 C 2
C 1 D 3
D 1 E 4
E 1 F 5
F 1 G 6
G 1 H 7
H 1 I 8
I 1 J 9
J 1 K 10
K 1 L 11
L 1 M 12
M 1 N 13
N 1 O 14
O 1 P 15
P 1 Q 16
Q 1 R 17
R 1 S 18
S 1 T 19
T 1 U 20
U 1 V 21
V 1 W 22
W 1 X 23
X 1 Y 24
Y 1 Z 25
26
A 2 B 1 Z 5
B 1 C 2
C 1 D 3
D 1 E 4
E 1 F 5
F 1 G 6
G 1 H 7
H 1 I 8
I 1 J 9
J 1 K 10
K 1 L 11
L 1 M 12
M 1 N 13
N 1 O 14
O 1 P 15
P 1 Q 16
Q 1 R 17
R 1 S 18
S 1 T 19
T 1 U 20
U 1 V 21
V 1 W 22
W 1 X 23
X 1 Y 24
Y 1 Z 25
26
A 2 B 17 C 41
B 2 C 1 D 48
C 2 D 4 E 53
D 2 E 45 F 23
E 2 F 7 G 55
F 2 G 46 H 25
G 2 H 10 I 57
H 2 I 47 J 27
I 2 J 60 K 59
J 2 K 37 L 40
K 2 L 2 M 61
L 2 M 5 N 24
M 2 N 38 O 63
N 2 O 8 P 26
O 2 P 39 Q 65
P 2 Q 11 R 28
Q 2 R 67 S 68
R 2 S 49 T 13
S 2 T 50 U 69
T 2 U 3 V 14
U 2 V 6 W 70
V 2 W 51 X 15
W 2 X 9 Y 71
X 2 Y 52 Z 16
Y 1 Z 72
26
A 8 B 17 C 41 D 18 E 42 F 19 G 43 H 20 I 44
B 4 C 1 I 48 J 21 K 29
C 3 D 4 K 53 L 54
D 3 E 45 L 23 M 31
E 3 F 7 M 55 N 56
F 3 G 46 N 25 O 33
G 3 H 10 O 57 P 58
H 3 I 47 P 27 Q 35
I 2 J 60 Q 59
J 4 K 37 Q 40 R 22 S 30
K 3 L 2 S 61 T 62
L 3 M 5 T 24 U 32
M 3 N 38 U 63 V 64
N 3 O 8 V 26 W 34
O 3 P 39 W 65 X 66
P 3 Q 11 X 28 Y 36
Q 2 R 68 Y 67
R 3 S 49 Y 12 Z 13
S 2 T 50 Z 69
T 2 U 3 Z 14
U 2 V 6 Z 70
V 2 W 51 Z 15
W 2 X 9 Z 71
X 2 Y 52 Z 16
Y 1 Z 72
0

答案：
99
198
122
15
15
325
305
465
369

#include <iostream>
#include <cstdlib>
#include <cstring>
#define MAX 100
#define MAXA 200
using namespace std;

struct node{
    char head;
    char tail;
    int weight;
};
struct limb{//记录生成树的枝干
    char member[MAXA];//该枝干中的节点
    int num;//总的节点数
};
int limbNum = 1;//枝干的数目

void sortEdge(node *edge[],int num)//将输入的边进行由小到大排序
{
    node* temp = NULL;
    int tag = 0;
    int n;
    tag = edge[0]->weight;
    for(n = 0;n < num;n++){
        if(edge[n]->weight < tag){
            temp = edge[n];
            for(int i = n-1;i >= 0;i--){
                if((edge[n]->weight > edge[i]->weight)){
                    for(int j = n-1;j > i;j--)
                        edge[j+1] = edge[j];
                    edge[i+1] = temp;
                    //cout<<i+1<<‘ ‘<<edge[i+1]->head<<‘ ‘<<edge[i+1]->tail<<endl;
                    break;
                }
                else if(i == 0){
                    for(int j = n-1;j >= 0;j--)
                        edge[j+1] = edge[j];
                    edge[0] = temp;
                    //cout<<i<<‘ ‘<<edge[i]->head<<‘ ‘<<edge[i]->tail<<endl;
                    break;
                 }
            }
         }
        tag = edge[n]->weight;
    }
}
int main()
{
    int num = 0;//记录总的村子数
    int edgeNum = 0;//当前记录到的边数
    char headVill;//每条路的起点和终点村子名
    int n = 0;//记录与每个村子相连的村子数
    int T[MAXA];
    int totalWeight = 0;
    node *edge[MAX];
    limb *Limb[MAX];
    cin>>num;
    while(num > 0){
        edgeNum = 0;
        memset(T,0,sizeof(int)*MAXA);
        totalWeight = 0;
    for(int i = 0;i < num-1;i++){//录入输入的各条边
            cin>>headVill;
            cin>>n;

            for(int j = 0;j < n;j++){
                edge[edgeNum] = new node;
                edge[edgeNum]->head = headVill;
                cin>>edge[edgeNum]->tail;
                cin>>edge[edgeNum]->weight;
                edgeNum++;
            }
    }
    sortEdge(edge,edgeNum);//排序完成
    int h = 0,t = 0;
    for(int k = 0;k < edgeNum;k++){
        h = (int)edge[k]->head;
        t = (int)edge[k]->tail;
        if((T[h] == 0) &&(T[t] == 0)){//表示生成树中还没有这两个节点，就加入生成树
            Limb[limbNum] = new limb;
            Limb[limbNum]->num = 0;
            Limb[limbNum]->member[Limb[limbNum]->num] = edge[k]->head;
            Limb[limbNum]->member[++(Limb[limbNum]->num)] = edge[k]->tail;

            T[h] = limbNum;
            T[t] = limbNum;
            //cout<<T[h]<<‘ ‘<<T[t]<<‘ ‘<<edge[k]->head<<‘ ‘<<edge[k]->tail<<‘ ‘<<edge[k]->weight<<endl;
            totalWeight += edge[k]->weight;
            limbNum++;
        }
        else if((T[h] == 0) && (T[t] != 0)){//有一个节点已经在生成树中，则将这条边加入到那个队伍中
             Limb[T[t]]->member[++(Limb[T[t]]->num)] = edge[k]->head;
            // cout<<T[h]<<‘ ‘<<T[t]<<‘ ‘<<edge[k]->head<<‘ ‘<<edge[k]->tail<<‘ ‘<<edge[k]->weight<<endl;
             T[h] = T[t];
             totalWeight += edge[k]->weight;
        }
        else if((T[h] != 0) && (T[t] == 0)){
            Limb[T[h]]->member[++(Limb[T[h]]->num)] = edge[k]->tail;
            //cout<<T[h]<<‘ ‘<<T[t]<<‘ ‘<<edge[k]->head<<‘ ‘<<edge[k]->tail<<‘ ‘<<edge[k]->weight<<endl;
             T[t] = T[h];
             totalWeight += edge[k]->weight;
        }
        else if((T[h] != 0)&&(T[t] != 0)){
            if(T[h] != T[t]){
                int big,small;
                if(Limb[T[h]]->num > Limb[T[t]]->num){
                    big = h;
                    small = t;
                }
                else{
                    big = t;
                    small = h;
                }
               // cout<<T[h]<<‘ ‘<<T[t]<<‘ ‘<<edge[k]->head<<‘ ‘<<edge[k]->tail<<‘ ‘<<edge[k]->weight<<endl;
                int b = Limb[T[big]]->num + 1;
                int c = Limb[T[small]]->num;
                int d = T[small];
               // cout<<"big"<<(char)big<<" small"<<(char)small<<endl;
               // cout<<Limb[T[big]]->num<<" "<<Limb[T[small]]->num<<endl;
                for(int a = 0;a <= c;a++){
                    Limb[T[big]]->member[b] = Limb[d]->member[a];
                   // cout<<Limb[d]->member[a]<<endl;
                    T[(int)Limb[d]->member[a]] = T[big];
                    b++;
                }
                Limb[T[big]]->num = b-1;
                totalWeight += edge[k]->weight;
            }
            //else
                //cout<<T[h]<<‘ ‘<<T[t]<<‘ ‘<<edge[k]->head<<‘ ‘<<edge[k]->tail<<‘ ‘<<edge[k]->weight<<endl;
        }
    }
    cout<<totalWeight<<endl;
    cin>>num;
    }
    return 0;
}

[HOJ]1632、[POJ]1251 Jungle Roads,布布扣,bubuko.com

[HOJ]1632、[POJ]1251 Jungle Roads

原文：http://blog.csdn.net/ymzmdx/article/details/21389373