混合圖歐拉回路
原來混合圖歐拉回路用的是網絡流。
把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數，那么肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數為偶數，存在奇數度點必不能有歐拉回路。
好了，現在每個點入度和出度之差均為偶數。那么將這個偶數除以2，得x。也就是說，對于每一個點，只要將x條邊改變方向（入>出就是變入，出>入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那么很明顯，該圖就存在歐拉回路。
現在的問題就變成了：我該改變哪些邊，可以讓每個點出 = 入？構造網絡流模型。首先，有向邊是不能改變方向的，要之無用，刪。一開始不是把無向邊定向了嗎？定的是什么向，就把網絡構建成什么樣，邊長容量上限1。另新建s和t。對于入 > 出的點u，連接邊(u, t)、容量為x，對于出 > 入的點v，連接邊(s, v)，容量為x（注意對不同的點x不同）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個？察看流值分配，將所有流量非0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。
由于是滿流，所以每個入 > 出的點，都有x條邊進來，將這些進來的邊反向，OK，入 = 出了。對于出 > 入的點亦然。那么，沒和s、t連接的點怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個既沒和s也沒和t連接的點，自然早在開始就已經滿足入 = 出了。那么在網絡流過程中，這些點屬于“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之后，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題，解了。
今天碰到一題是求這的...寫下筆記......
http://acm.pku.edu.cn/JudgeOnline/problem?id=1637
posted on 2008-08-02 22:09
小果子 閱讀(958)
評論(1) 編輯 收藏 引用