【模板】Prim - 最小生成树
我最常用的最小生成树算法 = 3=
-
#define N 505
-
#define MAX 65540
-
-
int n;
-
int edge[N][N];
-
int sum;
-
-
void prim(){
-
int i,j,k;
-
int lowcost[N];
-
bool visit[N]={false};
-
sum = 0;
-
for (i=0;i<n;i++){
-
lowcost[i]=edge[0][i];
-
}
-
visit[0]=true;
-
for (i=1;i<n;i++){
-
j=0;
-
while(visit[j]) j++;
-
for (k=0;k<n;k++)
-
if((!visit[k])&&(lowcost[k]<lowcost[j])) j=k;
-
sum = lowcost[j]>sum?lowcost[j]:sum;
-
visit[j]=true;
-
for (k=0;k<n;k++)
-
if (!visit[k]&&(edge[j][k]<lowcost[k])){
-
lowcost[k]=edge[j][k];
-
}
-
}
-
}
没连通的边长应为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比较好敲……幸好有做这题不然就忘了准备模板了囧
