本文主要是介绍POJ 1789最小生成树的水题，PRIM算法普通的实现版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意 读入有N个7位的字符串，定义每个字符串之间的距离是他们之间不同字符的个数，然后就是求最小生成树的水题了
这题用不同方法做了几遍了，废话就不说开了，
只是我第一次写PRIM算法
增点集。。。就是PRIM算法中节点不断增加的点的集合
减点集。。。与增点集相反的点集,其中的点不断减少,直到为零算法就结束了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#define INF 1e9
using namespace std;
int closest[2100]; //存的是最短边的在增点集的端点 ，数组的下标表示减集的点的编号
int lowcost[2100];//存最短边的数组，即增点集合的所有的点到数组下标代表的减点集合的点的最短距离
int m;//点的个数
char tu[2105][8];
int cal(int i,int j)//计算2个字串的距离
{int ans=0,ii=-1;while(++ii<7)if(tu[i][ii]!=tu[j][ii])ans++;return ans;
}
void read()
{for(int i=0;i<m;i++)scanf("%s",tu[i]);
}
void deal()//prim算法
{for(int i=0;i<m;i++) { lowcost[i]=INF;}//初始化 lowcost数组for(int i=0;i<m;i++) { closest[i]=0;}//初始化closest 数组 -1表示该点已经被选入增点的集合，否则在检点的集合closest[0]=-1;//加入第一个点int num=0,ans=0,e=0;//e代表最新加入增点集的点while(++num<m)//加入m-1条边{int micost=INF,miedge=-1;//micost代表当前的最短边，miedge代表当前最短边在减点集中的端点for(int i=0;i<m;i++)//更新最短边if(closest[i]!=-1)//选择减点集的点更新最短距离{int temp=cal(e,i);if(temp<lowcost[i]){lowcost[i]=temp;closest[i]=e;}if(lowcost[i]<micost)//更新当前的最短边micost=lowcost[miedge=i];}ans+=micost;closest[e=miedge]=-1;//加入新的点到减点集，同时更新增点集的点e，最新加入的点e}printf("The highest possible quality is 1/%d.\n",ans);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(cin>>m,m){read();deal();}return 0;
}
这篇关于POJ 1789最小生成树的水题，PRIM算法普通的实现版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
