prim 算法求最小生成树
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20712 Accepted Submission(s): 9213
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
Sample Output
3
5
Hint
Hint
Huge input, scanf is recommended.
Source
Recommend
JGShining
#include<stdio.h>
#include<string.h>
#define max 100000000
int map[][],sum,min;// map[i][j] 记录从点 i 到点 j 的距离 ！
int main()
{
int n,m,i,x,y,dis,j,flag,visit[];
while(~scanf("%d",&n)&&n!=)
{ m=(n*(n-))/;
memset(map, , sizeof(map));//数组清零
memset(visit,,sizeof(visit));
for(i=;i<m;i++)
{
scanf("%d%d%d",&x,&y,&dis);
map[x-][y-]=map[y-][x-]=dis;
}
for(i=;i<n;i++)
map[i][i]=max;//建图完成 ！
visit[]=; sum=;
for ( i=; i<n; i++)//prim 算法求最小生成树
{
min= ;
for ( j=; j<n; j++)
{
if (!visit[j] && map[][j] < min)
{
min = map[][j];
flag = j;
}
}
sum += min;
visit[flag] = ;
for ( j=; j<n; j++)
{
if (!visit[j] && map[][j] > map[flag][j])
{
map[][j] = map[flag][j];
}
}
}
printf("%d\n",sum);
}
return ;
}
prim写成函数的方式，更容易理解。
#include<stdio.h>
int map[][],visit[];
int length[];
int getmin(int n)
{
int i,min;
for(i=;i<=n;i++)
{
if(visit[i]==)
{
min=i;
break;
}
}
for(i++;i<=n;i++)
{
if(visit[i]==&&length[min]>length[i])
min=i;
}
return min;
}
int prim(int n)
{
int i,j;
int min;
int sum;
for(i=;i<=n;i++)
{
visit[i]=;
length[i]=map[][i];
}
visit[]=;
sum=;
for(i=;i<=n;i++)
{
min=getmin(n);
visit[min]=;
sum+=length[min];
for(j=;j<=n;j++)
{
if(visit[j]==)
{
if(map[min][j]<length[j])
{
length[j]=map[min][j];
}
}
}
}
return sum;
}
int main()
{
int n, m;
int i;
int min;
int u, v, cost;
while (scanf("%d", &n) != EOF && n != )
{
m = n * (n - ) / ;
for (i = ; i <= n; i++)
map[i][i] = ;
for (i = ; i < m; i++)
{
scanf("%d%d%d", &u, &v, &cost);
map[u][v] = cost;
map[v][u] = cost; }
min = prim(n);
printf("%d\n", min);
}
return ;
}
浓缩版：
#include<stdio.h>
#include<string.h>
#define MAX 100000
int map[][],v[];
int prim(int n)//最好的prim的模板。
{
int k[],i,j;
int min,sum=,flag,count=;
memset(k,,sizeof(k));
memset(v,,sizeof(v));
for(i=;i<=n;i++)
k[i]=map[][i];
for(i=;i<=n;i++)
{
min=MAX;
for(j=;j<=n;j++)
{
if(min>k[j]&&v[j]==)
{
min=k[j];
flag=j;
}
}
sum+=min;
v[flag]=;
for(j=;j<=n;j++)
if(v[j]==&&k[j]>map[flag][j]&&flag!=j)
k[j]=map[flag][j];
}
return sum;
}
int main()
{
int n,m,i,j,p,q,r,min;
while(~scanf("%d",&n)&&n!=)
{
m=n*(n-)/;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
if(i==j) map[i][j]=;
else
map[i][j]=MAX;
}
for(i=;i<m;i++)
{
scanf("%d%d%d",&p,&q,&r);
map[p][q]=map[q][p]=r;
}
min=prim(n);
printf("%d\n",min);
}
return ;
}