• <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>

            3336 ACM Underground

            Posted on 2010-03-03 15:00 王之昊 閱讀(245) 評論(0)  編輯 收藏 引用 所屬分類: pku
                題目大意是 alice 從 s 點做火車到 t點,但是想逃票, 路線是由若干條線路組成的,若兩條線路相交,那么可以轉車,路線上可能有警察,如果警察在交點上,那么你轉車他就會檢查你的票,不轉車他就不會管你 ; 如果警察在線路的其他位置,那么只要你碰到他,他就會檢查你。有最多100條線路,3000個警察。問 alice 是否能逃票成功。
                
                 關鍵是建圖。 把線路離散化,然后以子線段作為結點。如果直接把警察作為分割點的話,最后的子線段可能很多。在交點處的警察不應該作為分割點,他們只是表示這兩條線路不可轉車。剩余的在線路上的警察是分割點。
                 
                 先考慮一條線路,用分割點把它隔開。首先可以明確這些子線段不直接相連。考慮兩條線路間的關系。如果這兩條線路的交點上有警察,我們可以認為這兩條線路直接不相連。
                 
                 具體實現的第一步是確定哪些是分割點, 哪些不是。可以根據 對于每個警察,他在幾條線路上 判斷。如果他在0條線路上。不是分割點。如果他在1條線路上,是分割點。如果他在多條線路上,我認為這些線路間不具備直接相連性。
                 然后把分割點分到每條線路上去,去把每條線路分割成子線段。并且標明這些子線段不具有直接相連性。
                 然后考慮那些雖然相交,但是我們認為他們不直接相連的線路,把它們的子線段標記成不直接相連。
                 最后這些子線段的數量小于 n + m。算出剩余的兩兩子線段的關系。最后求一下連通塊即可。
                 
             

            posts - 26, comments - 7, trackbacks - 0, articles - 17

            Copyright © 王之昊

            亚洲中文久久精品无码| 国内精品伊人久久久久AV影院| 国产成人精品白浆久久69| 精品久久久久久久无码 | 99re这里只有精品热久久 | 久久精品国产亚洲Aⅴ香蕉| 三级片免费观看久久| 亚洲国产美女精品久久久久∴| avtt天堂网久久精品| 久久男人AV资源网站| 久久久久人妻一区二区三区vr | 中文字幕亚洲综合久久| 亚洲日韩欧美一区久久久久我| 日产精品久久久久久久性色| 99国内精品久久久久久久| 狠狠色丁香婷婷久久综合五月 | 国内精品伊人久久久久av一坑| 久久久久黑人强伦姧人妻| 精品国产福利久久久| 久久人做人爽一区二区三区 | 久久福利片| 国内精品伊人久久久久| 久久九九久精品国产免费直播| 国产99久久久国产精免费| 久久亚洲私人国产精品| 久久综合九色综合网站| 激情五月综合综合久久69| 日本久久久精品中文字幕| 久久久精品人妻一区二区三区四 | 国产精品美女久久久| 性做久久久久久久| 久久精品极品盛宴观看| 日本高清无卡码一区二区久久| 久久成人18免费网站| 国产三级观看久久| 国产高潮久久免费观看| 久久99国产亚洲高清观看首页 | 99久久精品国产一区二区| 精品精品国产自在久久高清| 99久久精品午夜一区二区| 99久久这里只有精品|