主题链接：

思维：一个一个点，每两行之间不懂得字符个数就看做是权值。然后用kruskal算法计算出最小生成树

我写了两个代码一个是用优先队列写的。可是超时啦，不知道为什么。希望有人能够解答。后面用的数组sort排序然后才AC。

code：

数组sort排序AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct edge{    int from;    int to;    int cost;};bool cmp(edge e1,edge e2){    return e1.cost
        
       
      
     

优先队列超时代码

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct edge{    friend bool operator<(edge e1,edge e2)    {        return e1.cost>e2.cost;    }    int from;    int to;    int cost;};edge e;priority_queue
         
           Q;int father[2005];int nn,n;int find(int x){    if(x!=father[x])    {        father[x]=find(father[x]);    }    return father[x];}void kruskal(){    int MST=0;    for(int i=0;i<2005;i++)    {        father[i]=i;    }    int num=0;    while(!Q.empty()&&num!=nn)    {        edge e=Q.top();        //printf("BBB%d %d %d\n",e.from,e.to,e.cost);        Q.pop();        int fx=find(e.from);        int fy=find(e.to);        if(fx!=fy)        {            father[fx]=fy;            MST+=e.cost;            num++;        }    }    printf("The highest possible quality is 1/%d.\n",MST);}int main(){    char str[2005][10];    int i,j;    while(scanf("%d",&n)==1&&n)    {        nn=0;        while(!Q.empty()) Q.pop();        for(i=0;i
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。