#include <iostream>
#include 
<vector>
#include 
<algorithm>

using namespace std;

struct Edge
{
    
int row;
    
int column;
    
int value;

    Edge()
    
{}

    Edge( 
int a, int b, int c )
        :row(a),column(b),value(c)
    
{}
}
;

bool operator<( Edge const& Itema, Edge const& Itemb )
{
    
return Itema.value> Itemb.value;
}


vector
<Edge> graph;
int          visite[2001];
char         ch[2001][8];

int find( int x )
{
    
if ( x!= visite[x] )
        
return find( visite[x] );

    
return x;
}


int distance( char str1[8], char str2[8] )
{
    
int num= 0;

    
for ( int i= 0; i< 8++i )
        
if ( str1[i]!= str2[i] )
            num
++;

    
return num;
}


int main()
{
    
int n;

    
while ( scanf("%d",&n), n )
    
{
        
for ( int i= 0; i< n; ++i )
            scanf(
"%s",ch[i] );

        graph.reserve ( n
+ 1 );

        
for ( int i= 0; i< n; ++i )
        
{
            
for ( int j= 0; j< i; ++j )
                graph.push_back (  Edge( j,i,distance( ch[i], ch[j] ) ) );
    
            visite[i]
= i;
        }


        make_heap( graph.begin (), graph.end () );
        
int sum= 0;
        
int num= 1;

        
while ( num< n )
        
{
            
int u,v;
            
if ( (u= find(graph[0].column))!= (v= find(graph[0].row ) ) )
            
{
                sum
+= graph[0].value;
                visite[v]
= u;
                num
++;
            }


            pop_heap( graph.begin (), graph.end () );
            graph.pop_back ();
        }


        printf( 
"The highest possible quality is 1/%d.\n", sum );

        graph.clear ();
    }


    
return 0;
}
posted on 2008-11-06 12:00 Darren 阅读(213) 评论(3)  编辑 收藏 引用

评论:
# re: Pku 1789 Truck History 2008-11-06 12:42 | infinity
这题好像就是一个最小生成树吧!  回复  更多评论
  
# re: Pku 1789 Truck History 2008-11-06 13:02 | Darren
@infinity
这是最小生成树, 我用的是kruskal算法  回复  更多评论
  
# re: Pku 1789 Truck History 2008-11-06 14:03 | ******
我的做法:
串两两比较,匹配他们,统计不同的字符数,然后就产生了一张抽象的权值图
然后prim  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理