#include  < iostream >
#include 
< set >
#include 
< limits >

using   namespace  std;

struct  Node
{
    
int  broad, price;
    Node()
{}
    Node(
int   & a, int & b)
        :broad(a),price(b)
    
{}
}
;

Node data[
100 ][ 100 ];
int   length[ 100 ];


int  main()
{
    
int  test;
    scanf(
" %d " , & test);

    
while ( test --  )
    
{
        
int  n;
        
set < int >  br;

        scanf(
" %d " , & n);

        
for  (  int  i =   0 ; i <  n;  ++ i )
        
{
            
int  d,x,y;
            scanf(
" %d " , & d);

            length[i]
=  d;
            
for  (  int  j =   0 ; j <  d;  ++ j )
            
{
                scanf(
" %d%d " , & x, & y);
                data[i][j]
=  Node(x,y);

                br.insert(x);    
//    Save all broad , use set to avoid repeating
            }

        }


        
set < int > ::iterator pos;
        
double  max =  numeric_limits < double > ::min();
        
for  ( pos =  br.begin (); pos !=  br.end ();  ++ pos )    //    for every broad
         {
            
int    t =   * pos;
            
int    total =   0 ;
            
bool   isok =   false ;

            
for  (  int  i =   0 ; i <  n;  ++ i )    //   n devices
             {
                
int  M =  INT_MAX;

                
for  (  int  j =   0 ; j <  length[i];  ++ j )
                    
if  ( data[i][j].broad >=  t  &&  data[i][j].price <  M )
                        M
=  data[i][j].price;       //    find  the min price

                
if  ( M ==  INT_MAX )
                
{
                    isok
=   true ;
                    
break ;
                }

                total
+=  M;     
            }


            
if  ( isok )  continue ;

            
if  ( ( double )t /  ( double )total >  max ) max =  ( double )t /  ( double )total;    //   update
        }


        printf(
" %.3lf\n " , max );
    }


    
return   0 ;
}
posted on 2008-10-01 22:06 Darren 阅读(519) 评论(2)  编辑 收藏 引用 所属分类: 图论搜索

评论:
# re: PKU 1018 Communication System 2008-11-04 10:28 | lxc0601
不知道如何证明?  回复  更多评论
  
# re: PKU 1018 Communication System 2008-11-05 09:42 | Darren
这就是一个穷举。 枚举每一种带宽, 用 set 可以避免重复。
然后再从n种设备中找出相应最小的 price 并计算总和

if ( data[i][j].broad>= t && data[i][j].price< M )
M= data[i][j].price;


total+= M;  回复  更多评论
  

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