关于最小生成树,普里姆算法

gascd

代码为hdu1102的错误答案
原题目:http://acm.hdu.edu.cn/showproblem.php?pid=1102

题目大意为, 有N(3<=N<=100)个村庄，需要给村庄之间修路。
每个村庄之间的距离范围是[1,1000]，其中已经修好了Q(0 <= Q <= N * (N + 1) / 2)条路。

输入:第一行输入整数N，在接下来N行输入矩阵。再输入整数Q，在接下来Q行，每行输入2个整数，代表两个村庄已经有修好的路。
输出:你需要修建的路的长度。

样例输入:
3
0 990 692
990 0 179
692 179 0
1
1 2

样例输出:
179

我的代码样例过了，自己又举了两个例子，也过了，但提交的时候，却显示错误答案，找了半天也没发现错误，求各路大神帮忙看看。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define INFINITY 65535
   
5. #define MAXVEX 100
   
6. 
   
7. typedef struct
   
8. {
   
9.         char vexs[MAXVEX];
   
10.         int arc[MAXVEX][MAXVEX];
    
11.         int numVertexes, numEdges;
    
12. }MGraph;
    
13. long long num = 0;
    
14. 
    
15. void CreateMGraph(MGraph *G)
    
16. {
    
17.         int i, j, q, m, n;
    
18. 
    
19.         scanf("%d", &G->numVertexes);
    
20.         for(i=0; i<G->numVertexes; i++)
    
21.         {
    
22.                 for(j=0; j<G->numVertexes; j++)
    
23.                 {
    
24.                         getchar();
    
25.                         scanf("%d", &G->arc[i][j]);
    
26.                 }
    
27.         }
    
28.         scanf("%d\n", &q);
    
29.         for(i=0; i<q; i++)
    
30.         {
    
31.                 scanf("%d %d", &m, &n);
    
32.                 G->arc[m-1][n-1] = 1;
    
33.                 G->arc[n-1][m-1] = 1;
    
34.                 num--;
    
35.         }
    
36. }
    
37. 
    
38. void prim(MGraph *G)
    
39. {
    
40.         int lowcost[MAXVEX];
    
41.         int min, i, j, k;
    
42. 
    
43.         for(i=0; i<G->numVertexes; i++)
    
44.         {
    
45.                 lowcost[i] = G->arc[0][i];
    
46.         }
    
47. 
    
48.         //实现过程
    
49.         for(i=0; i<G->numVertexes; i++)
    
50.         {
    
51.                 min = INFINITY;
    
52.                 j = 1;
    
53.                 k = 0;
    
54.                 while(j<G->numVertexes)
    
55.                 {
    
56.                         if(lowcost[j] != 0 && lowcost[j] < min)
    
57.                         {
    
58.                                 min = lowcost[j];
    
59.                                 k = j;
    
60.                         }
    
61.                         j++;
    
62.                 }
    
63.                 if(min != INFINITY)
    
64.                         num += min;
    
65.                 lowcost[k] = 0;
    
66.                 for(j=1; j<G->numVertexes; j++)
    
67.                 {
    
68.                         if(lowcost[j]!=0 && G->arc[k][j]<lowcost[j])
    
69.                         {
    
70.                                 lowcost[j] = G->arc[k][j];
    
71.                         }
    
72.                 }
    
73.         }
    
74.         printf("%d", num);
    
75. }
    
76. 
    
77. int main()
    
78. {
    
79.         MGraph G;
    
80.         CreateMGraph(&G);
    
81.         prim(&G);
    
82.         system("pause");
    
83.         return 0;
    
84. }

复制代码

gascd

贪心只能过样例