• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ?

            #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 閱讀(542) 評論(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;  回復  更多評論
              
            久久久久18| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 国产亚洲成人久久| 少妇熟女久久综合网色欲| 久久精品水蜜桃av综合天堂| 狠狠人妻久久久久久综合| 久久国产劲爆AV内射—百度| 99久久亚洲综合精品成人| 久久夜色精品国产噜噜亚洲a| 久久久久高潮毛片免费全部播放| 国内精品伊人久久久久影院对白| 精品熟女少妇a∨免费久久| 一级a性色生活片久久无| 日本精品久久久久中文字幕8| 久久久久亚洲AV片无码下载蜜桃| 精品久久综合1区2区3区激情| 国产精品久久久久无码av| 色综合久久久久无码专区 | 久久综合噜噜激激的五月天| 久久天天躁狠狠躁夜夜不卡| 国产99久久久国产精免费| 国产精品久久亚洲不卡动漫| 久久久久久久97| 久久久久人妻精品一区| 亚洲国产精品久久久天堂| 久久亚洲国产最新网站| 亚洲国产成人久久一区久久| 久久国产高清一区二区三区| 品成人欧美大片久久国产欧美| 亚洲国产二区三区久久| 亚洲国产精品久久66| 欧美久久综合性欧美| 久久免费精品一区二区| 青青热久久综合网伊人| 久久国产成人| 久久精品中文字幕大胸| 亚洲精品乱码久久久久久| 精品无码久久久久久午夜| 亚洲国产精品久久久久久| 四虎亚洲国产成人久久精品| 久久亚洲熟女cc98cm|