#P3263. 经销商问题
经销商问题
经销商问题
题目描述
CTY 是一名经销商,希望向其他经销商进货。共有 名经销商,编号 是库存无限的顶级经销商,编号 是 CTY。顶级经销商以固定单价 出货。
经销商之间有若干单向买卖关系。关系 允许 最多向 销售 件商品,每件的销售价格为该商品成本价的 倍。顶级经销商的出货始终按固定单价 。除顶级经销商和 CTY 外,每名经销商由进货取得的商品须全部出货。货物最终源自顶级经销商,可以经过多次转手。
求 CTY 最多能购入多少件商品,以及在购入件数达到最大时所需的最小总成本。
输入格式
第一行三个整数 ,分别表示经销商数、买卖关系数、顶级经销商的出货单价。
接下来 行,每行四个整数 ,表示一条从 到 的买卖关系、最多销售件数及加价百分数。对于所有从顶级经销商出发的关系,。数据没有重边。
输出格式
第一行输出最多能购入的件数。第二行输出该件数下的最小总成本,保留一位小数。无法购入商品时,两行依次输出 0 和 0.0。
样例
3 3 5
1 2 4 0
2 3 3 100
1 3 3 0
6
45.0
直接从经销商 购入 件,每件价格为 。再经由经销商 购入 件,每件价格为 。总成本为 。
数据规模与约定
,,。