#P3263. 经销商问题

经销商问题

经销商问题

题目描述

CTY 是一名经销商,希望向其他经销商进货。共有 nn 名经销商,编号 11 是库存无限的顶级经销商,编号 nn 是 CTY。顶级经销商以固定单价 ss 出货。

经销商之间有若干单向买卖关系。关系 u→vu\to v 允许 uu 最多向 vv 销售 cc 件商品,每件的销售价格为该商品成本价的 1+x/1001+x/100 倍。顶级经销商的出货始终按固定单价 ss。除顶级经销商和 CTY 外,每名经销商由进货取得的商品须全部出货。货物最终源自顶级经销商,可以经过多次转手。

求 CTY 最多能购入多少件商品,以及在购入件数达到最大时所需的最小总成本。

输入格式

第一行三个整数 n,m,sn,m,s,分别表示经销商数、买卖关系数、顶级经销商的出货单价。

接下来 mm 行,每行四个整数 u,v,c,xu,v,c,x,表示一条从 uu 到 vv 的买卖关系、最多销售件数及加价百分数。对于所有从顶级经销商出发的关系,x=0x=0。数据没有重边。

输出格式

第一行输出最多能购入的件数。第二行输出该件数下的最小总成本,保留一位小数。无法购入商品时,两行依次输出 0 和 0.0。

样例

3 3 5
1 2 4 0
2 3 3 100
1 3 3 0
6
45.0

直接从经销商 11 购入 33 件,每件价格为 55。再经由经销商 22 购入 33 件,每件价格为 1010。总成本为 45.045.0。

数据规模与约定

n≤1800n\le 1800,m≤n(n−1)/2m\le n(n-1)/2,0≤x≤1000\le x\le100。

BZOJ 归档题面