本文主要是介绍poj1789 PRIM算法优先队列版（STL框架），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意很简单 主要是想练一下优先队列的使用
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
bool vis[2100];
int m;//点的个数
char tu[2105][8];
struct node
{node(int i=0,int j=0,int k=0):a(i),b(j),len(k){}//构造函数int a,b,len;
};
struct cmp{ bool operator()(const node&a,const node&b) {return a.len>b.len;} };//比较函数类
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算法
{priority_queue<node,vector<node>,cmp>* que=new priority_queue<node,vector<node>,cmp>;memset(vis,0,sizeof(vis));int num=0,ans=0,e=0;node temp;while(++num<m)//加入n-1条边{vis[e]=1;//加入一个点for(int i=0;i<m;i++)//加入新的边if(!vis[i]&&i!=e)que->push( node(i,e,cal(e,i)) );while(vis[e])//找到合适的最短边{temp=que->top();que->pop();e=temp.a;if(!vis[temp.b]) e=temp.b;}ans+=temp.len;//加上距离}delete que;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;
}
这篇关于poj1789 PRIM算法优先队列版（STL框架）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
