问题描述:给定一条有向直线L及L上的n+1个点有向直线L上的每个点x<sub>i</sub>都有权值w(x<sub>i</sub>),每条

问题描述:给定一条有向直线L及L上的n+1个点<img src='https://img2.soutiyun.com/ask/2021-01-04/978633693635759.png' />有向直线L上的每个点x<sub>i</sub>都有权值w(x<sub>i</sub>),每条有向边<img src='https://img2.soutiyun.com/ask/2021-01-04/978633715425005.png' />都有一个非负边长<img src='https://img2.soutiyun.com/ask/2021-01-04/978633726123617.png' />.有向直线L上的每个点x<sub>i</sub>可以看作客户,其服务需求量为w(x<sub>i</sub>).每条边<img src='https://img2.soutiyun.com/ask/2021-01-04/978633744233653.png' />的边长<img src='https://img2.soutiyun.com/ask/2021-01-04/978633726123617.png' />可以看作运输费用.如果在点x<sub>i</sub>处未设置服务机构,则将点x<sub>i</sub>处的服务需求沿有向边转移到点x<sub>j</sub>处服务机构需付出的服务转移费用为<img src='https://img2.soutiyun.com/ask/2021-01-04/97863389506428.png' />在点x<sub>0</sub>处已设置了服务机构,现在要在直线L上增设m处服务机构,使得整体服务转移费用最小. 算法设计:对于给定的有向直线L,计算在直线L上增设m处服务机构的最小服务转移费用. 数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示有向直线L上除了点x<sub>0</sub>,还有n个点<img src='https://img2.soutiyun.com/ask/2021-01-04/978633863557478.png' />接下来的n行中,每行有2个整数.第i+1行的2个整数分别表示<img src='https://img2.soutiyun.com/ask/2021-01-04/978633838509045.png' />和<img src='https://img2.soutiyun.com/ask/2021-01-04/978633849623681.png' />. 结果输出:将计算的最小服务转移费用输出到文件output.txt. <img src='https://img2.soutiyun.com/ask/2021-01-04/978633970210578.png' />

时间:2023-02-15 14:24:26

相似题目