gascd 发表于 2017-2-7 17:45:32

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

本帖最后由 gascd 于 2017-2-7 17:49 编辑

代码为hdu1102的错误答案
原题目:http://acm.hdu.edu.cn/showproblem.php?pid=1102
题目大意为, 有N(3<=N<=100)个村庄，需要给村庄之间修路。
每个村庄之间的距离范围是，其中已经修好了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我的代码样例过了，自己又举了两个例子，也过了，但提交的时候，却显示错误答案，找了半天也没发现错误，求各路大神帮忙看看。
#include <stdio.h>
#include <stdlib.h>

#define INFINITY 65535
#define MAXVEX 100

typedef struct
{
      char vexs;
      int arc;
      int numVertexes, numEdges;
}MGraph;
long long num = 0;

void CreateMGraph(MGraph *G)
{
      int i, j, q, m, n;

      scanf("%d", &G->numVertexes);
      for(i=0; i<G->numVertexes; i++)
      {
                for(j=0; j<G->numVertexes; j++)
                {
                        getchar();
                        scanf("%d", &G->arc);
                }
      }
      scanf("%d\n", &q);
      for(i=0; i<q; i++)
      {
                scanf("%d %d", &m, &n);
                G->arc = 1;
                G->arc = 1;
                num--;
      }
}

void prim(MGraph *G)
{
      int lowcost;
      int min, i, j, k;

      for(i=0; i<G->numVertexes; i++)
      {
                lowcost = G->arc;
      }

      //实现过程
      for(i=0; i<G->numVertexes; i++)
      {
                min = INFINITY;
                j = 1;
                k = 0;
                while(j<G->numVertexes)
                {
                        if(lowcost != 0 && lowcost < min)
                        {
                              min = lowcost;
                              k = j;
                        }
                        j++;
                }
                if(min != INFINITY)
                        num += min;
                lowcost = 0;
                for(j=1; j<G->numVertexes; j++)
                {
                        if(lowcost!=0 && G->arc<lowcost)
                        {
                              lowcost = G->arc;
                        }
                }
      }
      printf("%d", num);
}

int main()
{
      MGraph G;
      CreateMGraph(&G);
      prim(&G);
      system("pause");
      return 0;
}

gascd 发表于 2017-2-7 17:52:26

贪心只能过样例{:5_104:}
页: [1]
查看完整版本: 关于最小生成树,普里姆算法