普及組難度網絡流複習

被坑過來搞網絡流了。
大概都不是很難的題。

不會網絡流怎麼辦?而。自行去做FASTFLOW。

難點和重點:
1.建模,常見模型算法
2.算法的選取
其實在OI界在發明什麼高端模型是比較難的事情了。。。掌握好已經存在的模型就很不錯了。

普通最大流

「CQOI2014 危橋」「OldBridges」额。我们考虑S向两个出发点连回路次数的边,结束点向汇点连回路次数的边,其余边为原图中是否存在的边,如果是危桥容量为1,否则为无限大。这样,当满流的时候证明图中有符合次数的从出发点到结束点的路径(显然有反着回来的,必定组成回路。)不过这样可能会求算出从a1->b2的情况。此时我们仅把其中一对起始和结束的关系交换再做一次即可。
「JSOI2010 Frozen Nova 冷冻波」
蛤了個蛤,居然判斷是否被遮蔽是的。笑死。
然後好像不能費用流。我們考慮二分時間。看看每次每個東西能發出多少邊。然後看看是否滿流就OK了。
脑残选手不会写两点式。

混合圖歐拉回路

「uva 10735」裸的。

動態加點模型

「HNOI 2007 緊急疏散」网上那些二分的思路是错的。具体原因:可能在某一个时间开始卡住很多人,额会把他们移到前面去。正确的做法是不断加点,在原有残余网络上跑最大流,直至流和空地相同。

最小割模型

「HNOI2013」切糕。就是裸的最小割啊,考虑一下如果有限制条件的话,就向高度比自己低D的点连无穷大的边即可。dinic选手去写了一发sap。233,其实根本就没有写。

「BoardPainting」
思考熊。本來想對每一個聯通塊搞兩次貪心的。然後被noname的這個測資hack了。

..###
.####
##...
##...
##...

額。好難啊。根本想不到怎麼建立模型。
题解讲的不知所云。
我们考虑每一个点有两个属性。down和right。我们记S集爲⬇集,T集爲➡集。我們對於一個點如果它不能向右延伸,我們認爲它是可down的。同理一個點可right也是一樣判定的。同時可行的時候連邊,表示這樣兩個點可以一起連向T。同理我們可以判定一起連向S的情況。而一個點最終只能屬於一個集合。這是一個最小割問題。

Recent Posts

comments powered by Disqus