【IOI2016】过山车铁路

题意:给你\(n\)段铁轨,每段铁轨要求进入时速度不大于\(s_i\),并且离开时速度恰好为\(t_i\),你每次可以花费\(1\)的代价将某一铁轨的离开速度减少\(1\),最后你要把铁轨按某一顺序连接在一起并且满足上面的约束,问花费的最小代价。

 

将速度离散化,强制每个铁轨的进入速度为\(s_i\),那么每条铁轨就相当于从\(s_i\)到\(t_i\)连一条边,并且可以任意从\(i\)到\(i+1\)连边来加速,花费\(1\)的代价从\(i+1\)向\(i\)连边来减速。那么问题转化为在这张图中找出一条从最小速度(可任意加速到起点)到最大速度(可由终点任意加速达到)的欧拉路径。

将所有题目给定的边连接后,按速度从小到大判断每个点的入度和出度是否相等。如果入度大于出度,那么需要从该点向下一个点连\(入度-出度\)条边,否则从下一个点向这个点连\(出度-入度\)条边,并计算相应的代价。当然,最小速度和最大速度要特殊处理。那么这时图就满足了欧拉路径的度数要求,但可能存在若干个连通块。

这时在添加一些边使得它们连通即可。即求一棵最小生成树。

说点什么

您将是第一位评论人!

提醒
wpDiscuz