• <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)論排行榜

            免费精品99久久国产综合精品| 99久久精品无码一区二区毛片| 久久只有这里有精品4| 香蕉99久久国产综合精品宅男自| 亚洲精品tv久久久久| 国产亚洲综合久久系列| 51久久夜色精品国产| 久久国产免费直播| 日韩亚洲欧美久久久www综合网| 久久www免费人成精品香蕉| 亚洲精品国精品久久99热一| 国产毛片久久久久久国产毛片 | 国产精品99久久久精品无码| 狠狠狠色丁香婷婷综合久久俺| 日本久久久久久久久久| 国产一区二区三区久久精品| 国产一区二区久久久| 久久青青草原精品国产软件| 国产韩国精品一区二区三区久久| 7777精品伊人久久久大香线蕉| 亚洲乱亚洲乱淫久久| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 久久国产精品99久久久久久老狼| 99久久香蕉国产线看观香| 久久国产成人午夜aⅴ影院| 久久精品国产亚洲av日韩| 亚洲综合伊人久久大杳蕉| 欧美亚洲国产精品久久高清| 国内精品伊人久久久久影院对白| 97久久久久人妻精品专区| 久久久久亚洲Av无码专| 乱亲女H秽乱长久久久| 无码AV中文字幕久久专区| 99久久综合国产精品免费| 伊色综合久久之综合久久| 日韩美女18网站久久精品| 亚洲国产精品无码久久久久久曰| 久久精品国产清自在天天线| 久久久中文字幕日本| 热综合一本伊人久久精品| 久久91精品国产91|