SRM 556

Brief description:

… 给定一个特殊的流网络。。(如果存在边,则边的流量为 2 或正无穷。。
。。求是否存在一个给定的 2-commodity_flow 。。。。

Analysis:

..250.二维状态暴力 bfs
… 500 .. 创建判定版本的问题(。带通配符。。逆向 dp 可解 (。。正向似乎也可以。不过逆向的剪枝力度要更强些。。
之后常规数位 DP。。正向逆向各跑一次。。。

… 1000 是一道考察建模的网络流题,(writer 的代码很嘲讽的写了一个暴力 dfs 增广。。而且每次只推 1 格流量。。。
参见 wata 在推上发的证明 。。 。(豪豪中译。。。

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

External link:

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