某島

… : "…アッカリ~ン . .. . " .. .

… 1000 是一道考察建模的網路流題,(writer 的代碼很嘲諷的寫了一個暴力 dfs 增廣。。而且每次只推 1 格流量。。。
參見 wata 在推上發的證明 。。 。(豪豪中譯。。。

250.。。
500。。。
1000.。。

External link:

http://en.wikipedia.org/wiki/Multi-commodity_flow_problem

September 15, 2012

SRM 556

Brief description:

… 給定一個特殊的流網路。。(如果存在邊,則邊的流量為 2 或正無窮。。
。。求是否存在一個給定的 2-commodity_flow 。。。。

Analysis:

..250.二維狀態暴力 bfs
… 500 .. 創建判定版本的問題(。帶通配符。。逆向 dp 可解 (。。正向似乎也可以。不過逆向的剪枝力度要更強些。。
之後常規數位 DP。。正向逆向各跑一次。。。