Brief description:
… 給定一個特殊的流網路。。(如果存在邊,則邊的流量為 2 或正無窮。。
。。求是否存在一個給定的 2-commodity_flow 。。。。
Analysis:
..250.二維狀態暴力 bfs
… 500 .. 創建判定版本的問題(。帶通配符。。逆向 dp 可解 (。。正向似乎也可以。不過逆向的剪枝力度要更強些。。
之後常規數位 DP。。正向逆向各跑一次。。。
… 1000 是一道考察建模的網路流題,(writer 的代碼很嘲諷的寫了一個暴力 dfs 增廣。。而且每次只推 1 格流量。。。
參見 wata 在推上發的證明 。。 。(豪豪中譯。。。
External link:
http://en.wikipedia.org/wiki/Multi-commodity_flow_problem