• <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>
            題意描述:
            給定字母表的前n個大些字母,以及這些字母間兩兩之間的大小關系(這樣的關系給定m組),問由這m組關系能否確定n個字母的整體順序,如果能輸出按續排列的字母。
            顯然,本題就是拓撲排序,不過題目的要求使得我們要處理一些細節。
            下面我先說以下拓撲排序:
            嚴蔚敏《數據結構》上的定義是:由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓撲排序
            直觀的說偏序指集合中僅有部分成員之間可比較,而全序指集合中全體成員之間均可比較。
            舉個例子,一個大的工程通常有許多小的工程組成,這些小工程之間通常存在某些先后順序;當然有些小工程之間不存在先后關系,它們是可以并行的。如果兩個小工程直接或間接的相互依賴,就是兩個小工程互為對方的先行條件,整個工程將無法進行下去。用一個個頂點分別表示這些小工程,用有向的邊表示小工程之間的依賴關系,我們可以得到一個有向圖。
            拓撲排序可以幫助我們確定這些小工程開始的順序,并且能夠判定小工程之間是否存在相互依賴(圖中是否有回路)。
            拓撲排序的具體做法是:
            1.在有向圖中選擇一個沒有前驅(入度為0)的頂點,輸出
            2.從圖中刪除該頂點和所有以它為尾的弧,并更新相關點的入度
            3.重復1,2步,直到所有頂點都被輸出,或者發現圖中存在回路。
            如果結合上面所舉的工程的例子,沒有依賴(先后)關系的工程是可以并行的,但是就本題(zoj1060)而言,它要求每兩個點之間的關系都是確定的,是不允許出現并行的,所以,當某一時刻,我們發現入度為0的點不止1個時,排序就失敗了。
            本題的輸出分為三種情況,并且要求輸出所用的條件個數,因此每增加一個條件就要做一次拓撲排序。
            以下是本題代碼,第一次寫,有點亂,將就一下把~~
            測試數據:http://poj.org/showmessage?message_id=133905

            posted on 2012-08-16 19:19 小鼠標 閱讀(1811) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            <2012年8月>
            2930311234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            隨筆分類(111)

            隨筆檔案(127)

            friends

            最新評論

            • 1.?re: 線段樹
            • 是這個樣子的,所以在OJ有時候“卡住”了也不要太灰心,沒準真的不是自己的原因呢。
              加油,祝你好運啦!
            • --小鼠標
            • 2.?re: 線段樹
            • 對于編程競賽來說,Java所需時間一般為C/C++的兩倍。合理的競賽給Java的時間限制是給C/C++的兩倍。
            • --傷心的筆
            • 3.?re: poj1273--網絡流
            • 過來看看你。
            • --achiberx
            • 4.?re: (轉)ubuntu11.10無法啟動無線網絡的解決方法
            • 膜拜大神。。查了一個下午資料終于在這里解決了問題。。神牛說的區域賽難道是ACM區域賽。。?
            • --Hang
            • 5.?re: 快速排序、線性時間選擇
            • 博主,謝謝你的文章。你的方法可以很好的處理分區基準在數組中重復的情況,書上的方法遇到這種輸入會堆棧溢出。書上給出了解釋但給的方法貌似不簡潔。
            • --lsxqw2004

            閱讀排行榜

            亚洲国产成人久久精品影视| 久久九九久精品国产| 婷婷综合久久中文字幕蜜桃三电影| 久久精品国产免费观看| 国内精品久久久久久久久电影网| 亚洲精品无码久久久久去q| 潮喷大喷水系列无码久久精品 | 精品久久久久久无码人妻热| 久久影院午夜理论片无码| 久久精品国产亚洲AV影院| 久久综合中文字幕| 久久人做人爽一区二区三区| 欧美一区二区精品久久| 亚洲精品tv久久久久久久久 | 2021久久国自产拍精品| 久久综合久久鬼色| 国产亚洲美女精品久久久久狼| 人妻少妇精品久久| 国产精品成人99久久久久91gav| 亚洲精品美女久久777777| 开心久久婷婷综合中文字幕| 国产精品久久久久9999| 亚洲精品无码成人片久久| 一本大道久久东京热无码AV| 国产99久久久国产精免费| WWW婷婷AV久久久影片| 久久久久亚洲精品无码蜜桃| 久久人妻AV中文字幕| 欧美与黑人午夜性猛交久久久| 久久久国产精品福利免费 | 亚洲国产小视频精品久久久三级 | 91麻豆国产精品91久久久| 开心久久婷婷综合中文字幕| 香蕉aa三级久久毛片| 欧美精品丝袜久久久中文字幕| 久久精品国产91久久麻豆自制 | 亚洲第一极品精品无码久久| 欧美精品丝袜久久久中文字幕| 久久精品国产亚洲5555| 免费一级欧美大片久久网| 亚洲伊人久久成综合人影院 |