@TaoSama
2017-03-28T21:51:51.000000Z
字数 1759
阅读 1107
个城市,条有向边,代表经过这条一次需要花费的代价 并且有的几率使得整个网络拥堵,要保证经过这条边的发生拥堵概率不超过 给出个仓库所在的城市,并给出,拥有的存储量 给出个需求所在的城市,并给出,拥有的存储量 输出最小花费,以及最小花费下最小化的拥堵概率
做法大概是: 拥堵概率计算,假设经过次, 反过来思考即, 最小化最大化,取个自然对数即 根据费用流问题需要最小化,取负就好了即 那么边权由变为了,并且这个数值是正的,不会有负圈的问题 对于双权只要把前一个权乘一个很大的值就可以了 这个是可以证明的,即新的权 对于不超过,即为,那么 之后跑多源多汇的费用流就可以了
是母串,是模式串,,,
问题抽象:假设现在有权值集合,每个权,形如 选择个权的子集,现要使得最大,相等的情况下,其次最大 现要将双权问题转化成单权问题 由问题可知,需构造某种映射方案使得满足原本的偏序关系 即令,,若,那么 构造如下方案:令,对于,则 同理,,则 同理,,则 易知,任意,且有,满足自反性 易知,若且,即且,可得,满足反对称性 易知,若且,即且,可得,满足传递性 所以,构造方案满足原本的偏序关系,原问题得证