SDUT 3362 数据结构实验之图论六：村村通公路

数据结构实验之图论六：村村通公路

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

当前农村公路建设正如火如荼的展开，某乡镇政府决定实现村村通公路，工程师现有各个村落之间的原始道路统计数据表，表中列出了各村之间可以建设公路的若干条道路的成本，你的任务是根据给出的数据表，求使得每个村都有公路连通所需要的最低成本。

Input

连续多组数据输入，每组数据包括村落数目N(N <= 1000)和可供选择的道路数目M(M <= 3000)，随后M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1～N编号。

Output

输出使每个村庄都有公路连通所需要的最低成本，如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。

Example Input

Example Output

DQE:

解法一（推荐）：普里姆算法。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <climits>
 4 
 5 using namespace std;
 6 
 7 #define MVN 1010
 8 
 9 typedef struct AdjMatrix
10 {
11     int w;
12     char *info;
13 }AM;
14 
15 typedef struct MGraph
16 {
17     int vex[MVN];
18     AM arc[MVN][MVN];
19     int vexn,arcn;
20 }MG;
21 
22 void creat(MG &G)
23 {
24     int i,j,w,k;
25     for(i=1;i<=G.vexn;i++)
26         for(j=1;j<=G.vexn;j++)
27             G.arc[i][j].w=INT_MAX;
28     for(k=1;k<=G.arcn;k++)
29     {
30         scanf("%d %d %d",&i,&j,&w);
31         G.arc[i][j].w=G.arc[j][i].w=w;
32     }
33 }
34 
35 struct{int i,w;}C[MVN];        //辅助数组{树上最近顶点编号，到该顶点距离}
36 int Mini(MG &G,int &sum)
37 {
38     int count=0;    //统计树上顶点
39     int i,j,k,min;
40     //初始化辅助数组
41     for(i=1;i<=G.vexn;i++)
42     {
43         C[i].i=1;
44         C[i].w=G.arc[1][i].w;
45     }
46     C[1].w=0;
47     count++;
48     //将最近的顶点加入树
49     for(k=2;k<=G.vexn;k++)
50     {
51         min=INT_MAX;
52         i=-1;
53         for(j=1;j<=G.vexn;j++)
54             if(C[j].w>0)
55                 if(C[j].w<min)
56                 {
57                     i=j;
58                     min=C[j].w;
59                 }
60         if(i==-1)    //没有可加顶点时返回至调用处
61             return count;
62         sum+=C[i].w;
63         C[i].w=0;
64         count++;
65         //新顶点入树后更新辅助数组
66         for(j=1;j<=G.vexn;j++)
67             if(G.arc[i][j].w<C[j].w)
68             {
69                 C[j].i=i;
70                 C[j].w=G.arc[i][j].w;
71             }
72     }
73     return count;
74 }
75 
76 int main()
77 {
78     MG G;
79     while(scanf("%d %d",&G.vexn,&G.arcn)!=EOF)
80     {
81         creat(G);
82         int sum=0;    //距离之和
83         if(Mini(G,sum)==G.vexn)
84             printf("%d
",sum);
85         else
86             printf("-1
");
87     }
88     return 0;
89 }
90 
91 /***************************************************
92 User name: ***
93 Result: Accepted
94 Take time: 0ms
95 Take Memory: 184KB
96 Submit time: 2016-11-17 19:14:49
97 ****************************************************/

解法二（不推荐）：最小生成树问题，学会使用countw数组连接下一个顶点，配合深度优先搜索判断公路是否连通，效率低下难懂，改用循环更佳。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <climits>    //INT_MAX
  4 
  5 using namespace std;
  6 
  7 #define MVN 101
  8 
  9 typedef struct AdjMatrix
 10 {
 11     int w;
 12     char *info;
 13 }AM;
 14 
 15 typedef struct MGraph
 16 {
 17     int vex[MVN];
 18     AM arc[MVN][MVN];
 19     int vexnum,arcnum;
 20 }MG;
 21 
 22 struct ue
 23 {
 24     int pr;
 25     int w;
 26 }countw[MVN],mi;
 27 
 28 void creat(MG &G)
 29 {
 30     int i,j,w,k;
 31     for(k=1;k<=G.vexnum;k++)
 32         G.vex[k]=k;
 33     for(k=1;k<=G.arcnum;k++)
 34     {
 35         scanf("%d %d %d",&i,&j,&w);
 36         G.arc[i][j].w=w;
 37         G.arc[j][i].w=w;
 38     }
 39 }
 40 
 41 int count,sum;
 42 void DFS(MG &G,bool *visited,int i)
 43 {
 44     count++;
 45     visited[i]=true;
 46     int k;
 47     mi.w=INT_MAX;
 48     mi.pr=0;
 49     for(k=1;k<=G.vexnum;k++)
 50     {
 51         if(countw[k].w<mi.w && visited[k]==false)
 52         {
 53             mi.pr=k;
 54             mi.w=countw[k].w;
 55         }
 56     }
 57     if(mi.pr!=0)
 58     {
 59         for(k=1;k<=G.vexnum;k++)
 60         {
 61             if(countw[k].w>G.arc[k][mi.pr].w)
 62             {
 63                 countw[k].pr=mi.pr;
 64                 countw[k].w=G.arc[k][mi.pr].w;
 65             }
 66         }//更新countw
 67         sum+=G.arc[countw[mi.pr].pr][mi.pr].w;
 68         DFS(G,visited,mi.pr);
 69     }
 70 }
 71 
 72 int main()
 73 {
 74     MG G;
 75     while(scanf("%d %d",&G.vexnum,&G.arcnum)!=EOF)
 76     {
 77         int k,o;
 78         for(k=1;k<=G.vexnum;k++)
 79         {
 80             for(o=1;o<=G.vexnum;o++)
 81             {
 82                 G.arc[k][o].w=INT_MAX;
 83             }
 84         }//邻接矩阵初始化
 85         creat(G);
 86         bool visited[MVN]={false};
 87         for(k=1;k<=G.vexnum;k++)
 88         {
 89             if(G.arc[1][k].w<INT_MAX)
 90             {
 91                 countw[k].pr=1;
 92                 countw[k].w=G.arc[1][k].w;
 93             }
 94             else
 95                 countw[k].w=INT_MAX;
 96         }
 97         count=0;
 98         sum=0;
 99         DFS(G,visited,1);
100         if(count==G.vexnum)
101             printf("%d
",sum);
102         else
103             printf("-1
");
104     }
105     return 0;
106 }
107 
108 /***************************************************
109 User name: ***
110 Result: Accepted
111 Take time: 0ms
112 Take Memory: 172KB
113 Submit time: 2016-11-09 21:00:48
114 ****************************************************/