题目:http://uoj.ac/problem/236

我们针对每个速度离散化之后建一个点可以知道题目中

减速需要花费1的代价 加速不需要代价

那么我们就把每个速度s->t连边 那么可以知道对于每一段

x-1,x来说左右如果s->t的个数大于t->s的个数那么 显然我需要花费代价 其他情况下不需要花费代价https://blog.csdn.net/u014609452/article/details/53996440可以参照图理解

然后处理出这样的东西之后我们知道每个边必须遍历一遍是欧拉图

我们对于s->t个数多的这么一个显然是需要花费多的代价

最后欧拉图需要保证全部联通 我用并查集 把不连通的那些边取出来 做最小生成树即可

 

分类: 并查集欧拉图

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论