almost 3 years ago

题目大意

一个环上有个车站和个办公室,给出每个火车站和办公室的坐标,以及环的大小
任务是要你求出一种车站和办公室的匹配方案使得总距离和最小。

分析

膜了一发将狼踩尽的题解才知道做法的QAQ
我们可以发现,如果不是一个环的话,最优解一定是一个类似括号序列的东西。
其次我们可以证明存在最优方案满足有一条弧不被匹配线给覆盖,这个我们通过调整匹配的方式即可。
现在我们的目标就是找到一条弧,砍掉之后的答案最优。
我们从每条边的贡献考虑,即长度×覆盖次数。我们记办公室为,火车站为,那么统计出来的一个覆盖次数的相对关系是不会变的。因此我们随意固定一个点求出一个相对关系,然后覆盖次数从小到大找到最优答案对应的要删去哪条边就行了。
看不懂的你就看代码咯= =
sgu313.cpp

← bzoj3153:AAA树 树上莫队 →
 
comments powered by Disqus