• <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>
            posts - 74,  comments - 33,  trackbacks - 0
            Taxi

            Time Limit: 1 Second ???? Memory Limit: 32768 KB

            As we all know, it often rains suddenly in Hangzhou during summer time.I suffered a heavy rain when I was walking on the street yesterday, so I decided to take a taxi back school. I found that there were n people on the street trying to take taxis, and m taxicabs on the street then. Supposing that the cars waited still and each person walked at a speed of v, now given the positions of the n persons and the m taxicabs, you should find the minimum time needed for all the persons to get on the taxicabs. Assume that no two people got on the same taxicab.

            Input

            For each case, you are given two integers 0 <= n <= 100 and n <= m <= 100 on the first line, then n lines, each has two integers 0 <= Xi, Yi <= 1000000 describing the position of the ith person, then m lines, each has two integers 0 <= xi, yi <= 1000000 describing the position the ith taxicab, then a line has a float 0.00001 < v <= 10000000 which is the speed of the people.

            Output

            You shuold figue out one float rounded to two decimal digits for each case.

            Sample Input

            2 3
            0 0
            0 1
            1 0
            1 1
            2 1
            1
            

            Sample Output

            1.00
            本來以為是dp求解的,后來誤以為KM做了一下,無果,后來想了想類似Max_Match搜索TLE
            后來找到了這句話
            -----------------------------------------------------------------------
            n個(gè)人乘坐m個(gè)的(dˉe),已知人和的的坐標(biāo)和人的速度,問每個(gè)人都打上
            的的最短時(shí)間。假設(shè)的的位置不能變且沒有兩個(gè)人打同一個(gè)的。
            假設(shè)T時(shí)間內(nèi)大家都可以打上的,那么對于t > T的時(shí)間,大家也可以
            打上的。因此,問題可以二分求解。
            對于給定的T,如果人可以在該時(shí)間內(nèi)走到某個(gè)的的位置,就在人和的
            之間連一條邊。于是問題的可行就要求該二分圖的最大匹配數(shù)等于n。求
            二分圖最大匹配可以用Hungary算法。


            ----------------------------------------------------------------
            來源:http://cuitianyi.com/ZOJ200901.pdf
            就居然明白了原來類最小最優(yōu)比例生成樹,我二分的時(shí)候是利用最大時(shí)間上限t二分 每次原圖中T<=t建圖得到
            邊 1 ,否則無邊。。結(jié)構(gòu)很無情TLE,看了一下數(shù)據(jù)范圍 1000000 0.00001 < v <= 10000000 郁悶。
            隨后改成把所有時(shí)間存儲(chǔ)在Time數(shù)組中然后在數(shù)組中二分 不幸的是CE。Faint!!
            原來是自己用了link做了數(shù)組標(biāo)號(hào),而C++優(yōu)link函數(shù)。。。。。。A的很曲折。膜拜大牛的解題報(bào)告給了二分的思路
            (今天我是想不到)
            部分代碼如下:
            double?dis(NODE?a,NODE?b){
            ????
            return?sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));????
            }

            bool?DFS(int?x){
            ????
            for(int?i=0;i<m;i++)
            ????????
            if(mark[x][i]&&!visited[i]){
            ????????????visited[i]
            =true;
            ????????????
            if(linkn[i]==-1||DFS(linkn[i])){
            ????????????????linkn[i]
            =x;
            ????????????????
            return?true;????
            ????????????}
            ????
            ????????}

            ????
            return?false;????????
            }

            bool?Max_Match(){
            ????
            int?i,sum=0;
            ????memset(linkn,
            0xff,sizeof(linkn));
            ????
            for(i=0;i<n;i++){
            ????????memset(visited,
            0,sizeof(visited));
            ????????DFS(i);
            ????}

            ????
            for(i=0;i<m;i++)
            ????????
            if(linkn[i]!=-1)sum++;
            ????
            if(sum==n)return?true;
            ????
            else?return?false;????
            }

            void?change(double?x){
            ????
            for(int?i=0;i<n;i++)
            ????????
            for(int?j=0;j<m;j++)
            ????????????
            if(x>=map[i][j])mark[i][j]=true;
            ????????????
            else?mark[i][j]=false;????
            }
            posted on 2009-04-17 14:32 KNIGHT 閱讀(161) 評(píng)論(0)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            91精品国产综合久久婷婷| 欧美亚洲日本久久精品| 国产亚洲精品美女久久久| 99久久99久久| 日本精品久久久久影院日本| 麻豆国内精品久久久久久| 成人午夜精品无码区久久| 精品999久久久久久中文字幕| 99久久精品费精品国产| 久久无码AV中文出轨人妻| 一本一道久久精品综合| 久久人人爽人人爽人人AV东京热| 亚洲综合婷婷久久| 国产精品99久久免费观看| 性做久久久久久久久浪潮| 99久久精品国产一区二区三区| 久久久久久国产a免费观看黄色大片 | 人妻无码久久一区二区三区免费 | 91精品国产色综合久久| 午夜精品久久久久久| 亚洲国产成人久久精品影视| 色综合久久久久久久久五月| 久久精品视屏| 国产精品伦理久久久久久| 97久久精品人妻人人搡人人玩| 波多野结衣久久精品| 亚洲欧美精品一区久久中文字幕| 99久久国产亚洲高清观看2024 | 久久精品国产2020| 色综合久久天天综线观看| 18岁日韩内射颜射午夜久久成人| 久久精品国产亚洲AV无码麻豆| 久久国产欧美日韩精品| 老男人久久青草av高清| 亚洲欧美一区二区三区久久| 综合久久精品色| 成人午夜精品无码区久久| 久久久久久久97| 久久午夜无码鲁丝片| 精品久久久久久久久午夜福利| 久久精品国产精品亚洲毛片|