日記12（網絡流看題總結）

     今天一直是在看網絡流的題和網絡流的模組化方法，從昨天的了解一點網絡流的皮毛，到現在已經對網絡流的解題方法有一定的感覺了。但一定還是比較模糊，不夠熟練。

Edelweiss神的《網絡流模組化彙總》pdf來看的這裡面寫的模組化方法技巧非常詳細，很是神奇，期間有些定義等理論知識和一定算法要看Amber的《最小割模型在資訊學競賽中的應用 》pdf，大約網絡流的模組化分為最大流的模組化，最小割的模組化，有上下界的最大流模組化，最小費用的模組化。

Edelweiss神說，沒有一套通用的方法，但我看了感覺和前兩種差不多，不過加了費用的權值限制。

    我看了這些題，感覺到，模組化可以從很多方面入手，比如，我昨天看的按照流平衡來了解模組化。其實還有串一邊題意當作一條增廣路的模組化方法，比如，足球比賽的題，有i場比賽，j個隊伍，要求第支隊伍必須勝場最多，我們就可以這樣像，第i場比賽有兩個隊伍比，第j個隊伍勝利了，然後勝場數加一或者加分，獲得一個增廣路增加的流，這樣把所有的比賽都建成一個圖，每場比賽和s相連，每隻隊伍就和t點相連，這樣再加上限制條件，就建圖成功。還可以把集合分成兩類，s集，t集，這應該算是最小割的模組化法吧，反正能做出題就是好方法，找出s集到t集的一種關系，進行連線構圖，就是一個建圖方法。其實建圖的時候還可以這樣考慮，把s點和供應方（隻是一種了解方法）相連，作為一種物品或分數或抽象物的供應方，t點和需求方相連，無論它需求什麼，一般可以在s點和供應方的邊容量是供應數的限制，而t和需求方是需求數的限制，當然不是每道題都有，而供應方和需求方之間的連線往往是題目中給的很多限制條件或必須的供需方。

    當然，建圖的方法有很多，完全靠我們的思維和腦洞大開，我感覺，這類題目一定要在題目中的各色各樣的條件中理清思路，這樣才能把每個條件配置設定好位置，要不然腦子裡亂哄哄一片，什麼圖也想不起來。

    昨天還打了cf，讓我知道很多做過的題的改編也是很可怕的，昨天的cf讓我感覺就是經典題目的改編，一個括号比對問題，加上一個問好，這個題就變了，雖然還可以和以前做過的一道括号比對問題有類似的解法，但模拟不全的話，是很難ac的。

    今天中午沒睡覺，哎其實中午沒怎麼睡過，還不如幹一些事情那，因為我字典樹，kmp都看過，雖然沒做過題，但也看過幾道，就學習了一下ac自動機的知識點和模闆，感覺ac自動機的原理和kmp非常相似，明白了kmp，裡ac自動機也就不遠了，感覺這就是在字典樹上的kmp算法，雖然原理很容易懂，但是代碼不是那麼好了解，因為大部分人都是用的數組模拟隊列來寫的，看起來不是很習慣，如果是有一個用隊列寫的代碼，那麼對照例題看起來應該會比較輕松了，然後再對照隊列寫法的代碼了解優化過的代碼，我感覺如果這樣做會比較輕松的掌握好ac自動機的模闆，至于題目，我不看都知道有很多，我也就不看了，我也隻是了解一下知識，以後有時間就把ac自動機的題目給補上，掌握它。