Liny_@NotePad

沉迷ACG中

【模板】Prim - 最小生成树

YOYO posted @ 2008年12月07日 20:52 in 【算法】与【数据结构】 with tags prim 最小生成树 , 2582 阅读

  我最常用的最小生成树算法 = 3=

  1. #define N 505
  2. #define MAX 65540
  3.  
  4. int n;
  5. int edge[N][N];
  6. int sum;
  7.  
  8. void prim(){
  9. int i,j,k;
  10.                 int lowcost[N];
  11.                 bool visit[N]={false};
  12.                 sum = 0;
  13.                 for (i=0;i<n;i++){
  14.                         lowcost[i]=edge[0][i];
  15.                 }
  16.                 visit[0]=true;
  17.                 for (i=1;i<n;i++){
  18.                         j=0;
  19.                         while(visit[j]) j++;
  20.                         for (k=0;k<n;k++)
  21.                                 if((!visit[k])&&(lowcost[k]<lowcost[j])) j=k;
  22.                         sum = lowcost[j]>sum?lowcost[j]:sum;
  23.                         visit[j]=true;
  24.                         for (k=0;k<n;k++)
  25.                                 if (!visit[k]&&(edge[j][k]<lowcost[k])){
  26.                                         lowcost[k]=edge[j][k];
  27.                                 }
  28.                 }
  29. }

没连通的边长应为MAX。
求最大生成树时为0，修改两个小于号即可。

结点是从0到N。

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter