Liny_@NotePad

沉迷ACG中

【模板】Prim - 最小生成树

  我最常用的最小生成树算法 = 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。

Bad Cowtractors

pku 2377:http://acm.pku.edu.cn/JudgeOnline/problem?id=2377

很基础的一道题,输入N和M,表示有N个结点和M条路径,求这个图的最大生成树。

题目意思很明显了,但是注意有重边的情况,此时应该输出权较大的结果,当不能连通时输出-1。

Agri-Net

pku 1258:http://acm.pku.edu.cn/JudgeOnline/problem?id=1258

最小生成树。prim或kruskal。由于prim比较好敲……幸好有做这题不然就忘了准备模板了囧