prim算法水题

样例：

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define INF 99999
using namespace std;


int a[30][30];
//查找是否具有相同的头
int f[30];
//结构体
struct Node
{
int x,y,z;


}node[30];


//排序:从小到大
bool cmp(Node p1,Node p2)
{
return p1.z<p2.z;


}
//并查集的中心（重点）
int find(int x)
{
if(f[x]==x) return x;
else
{
return f[x]=find(f[x]);
}
}


int main()
{
memset(a,-1,sizeof(a));
memset(f,0,sizeof(f));
int n;
char zm;
int b;
while(cin>>n&&(n!=0))
{
//初始化
for(int i=1;i<=n;i++)
{
a[i][i]=0;
}
//转化为邻接矩阵
for(int i=1;i<n;i++)
{
cin>>zm>>b;

for(int j=1;j<=b;j++)
{
char zm1;
int indext;
int b1;
cin>>zm1>>b1;
indext=zm1-64;
a[i][indext]=b1;
a[indext][i]=b1;
}
}
//*****
//测试代码：(看是否转为邻接矩阵)
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<a[i][j];
}
cout<<endl;
}
*/
//******
int m=1;
for(int i=1;i<=n;i++)
{
f[i]=i;
for(int j=1;j<=n;j++)
{
if(i<j&&(a[i][j]!=(-1)))
{
node[m].x=i;
node[m].y=j;
node[m].z=a[i][j];
m++;
}


}
}
//排序
sort(node+1,node+m,cmp);
int ans=0;
for(int i=1;i<m;i++)
{
int x=find(node[i].x);
int y=find(node[i].y);
if(x!=y)
{
ans+=node[i].z;
f[y]=x;
}
}
cout<<ans<<endl;


}
return 0;
}

最后

以上就是友好白昼为你收集整理的prim算法水题的全部内容，希望文章能够帮你解决prim算法水题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。