【图论】【建模】IOI2016 railroad

题目描述

Anna 在一个游乐园工作。她负责建造一个新的过山车铁路。她已经设计了影响过山车速度的 \(n\) 个特殊的路段（方便起见标记为 \(0\) 到 \(n-1\)）。现在 Anna 必须要把这些特殊的路段放在一起并提出一个过山车的最后设计。为了简化问题，你可以假设过山车的长度为零。

对于 \(0\) 和 \(n-1\) 之间的每个 \(i\)，这个特殊的路段 \(i\) 具有如下两个性质：

• 当进入这个路段时，有一个速度限制：过山车的速度必须小于或等于 \(s_i\) \(\text{km/h}\)（每小时千米）。

• 当离开这个路段时，过山车的速度刚好是 \(t_i\) \(\text{km/h}\)，不管过山车进入该路段时的速度如何。

最后完成的过山车设计是一个以某种顺序包含这 \(n\) 个特殊路段的单一铁路线。这 \(n\) 个路段中的每一个应当被使用刚好一次。连续的路段之前用铁轨来连接。Anna 应该选择这 \(n\) 个路段的顺序，然后确定每段铁轨的长度。铁轨的长度以米来衡量，可以是任意的非负整数（可以为零）。

两个特殊路段之间的每 \(1\) 米铁轨可以将过山车的速度减慢 \(1\) \(\text{km/h}\)。在这个过山车铁路的起点，过山车按照 Anna 选择的顺序进入第一个特殊路段时的速度是 \(1\) \(\text{km/h}\)。

最后的设计还必须满足以下要求：

• 过山车在进入这些特殊路段时不能违反任一个速度限制。

• 过山车的速度在任意时刻为正。

你的任务是找出这些路段之间铁轨的最小可能总长度（这些路段之间铁轨总长度的最小值）。

算法描述

嘿嘿，这是个图论题

翻译题面：有\(n\)个轨道，进入速度恰好为\(s_{i}\)，出速度为\(t_i\)，降速\(x\)花费代价\(x\)，提速无代价，求轨道的最小排列。

解释下为什么可以看作\(s_i\)，观察原题面，我们将相邻元素分为两种情况：

1. \(t_i > s_{i + 1}\) : 由于从\(i + 1\)出去时值一定是\(t_{i + 1}\)，所以最短一定最优，将速度（原题面）刚好降到\(s_{i + 1}\)。

2. \(t_i \leq s_{i + 1}\) : 不用降速，耗费为0，加速耗费也为0，可以看作加到了\(s_{i + 1}\)

如果将一个数带进这个排列模拟其变化（即原题的坐过山车），我们发现，对于每一个\(s_i、t_i\)，一定有一个时刻的速度等于它，并且由一个“\(inf\)”状态进入\(t_1\)，且从最后一个\(s_n\)回到这个"\(inf\)"状态。也就是说，如果我们把包含\(inf\)在内的每一种速度看作一个节点，那么一趟过山车一定会经过每一个节点（可能不止一次）。

所以我们将速度离散化。试图将它转化成边的问题，我们对于每一条轨道，将\(s_i\)向\(t_i\)连一条有向边，长度为0，代表花费0代价就可以经过这条轨道，我们发现这条边在从\(inf\)出发到\(inf\)的路径中是必走的边，这启发我们构造一个最短欧拉回路，让每条边必经过一次，边权和就是答案。一开始这些点都是不相通的，所以用一个并查集维护点的连通性。

首先将\(s_i\)到\(t_i\)之间的边连好，再连\(max\{s_i,t_i\}\)到\(inf\)的边和\(inf\)到\(1\)的边（边权是0所以不用计入答案）。接着我们要将添加权值最小的边使得其成为一个欧拉回路，我们对于\(i \in \{S,T\}\)，将\(i\)向\(i + 1\)连边。我们发现跨过很多个点连边的代价和与相邻点连边代价之和是一样的，所以每个点都只和相邻的点连边，并且对于每个点，对于覆盖这个点的一些边，向左和向右的数量应该是一样的，所以先前添加\(s_i\to t_i\)的时候，在离散化数组中将\(s_i\)加1，\(t_i\)减一，然后做一遍前缀和，可以发现，\(sum_i > 0\)代表向右的边更多，\(|sum_i|\)就是多出来的个数，所以我们从\(i + 1\)到\(i\)连\(|sum_i|\)条边，每条边权为\(v_{i + 1} - v_i\)（\(v\)是离散化数组）。由于这些边是为了构造欧拉回路而生的，所以必须连，直接将边权加进答案，后文同理。

（记得连边时并查集上合并两端点）

这时检查答案，发现我们事实上将这个图连成了若干子欧拉回路，要合并这些回路，就要在它们之间建一条双向边，其中提速边为0，降速边为\(|v_u -v_v|\)。同上文，在相邻两点之间连边一定是最优的，所以直接遍历一遍节点，如果\(i\)和\(i + 1\)在并查集中不连通，就在它们之间加一条边权为\(v_{i + 1} - v_i\)的边，因为节点间的连通性不规律，所以这样相邻连边最后连下来是一个图，将这些新加的边跑一次最小生成树即可，树边计入答案。

不愧是IOI题目

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5,inf = 1e9 + 7;
struct Edge{
	int u,v;long long w;
}e[N * 4];
long long n,m,s[N],t[N],v[N * 4],sum[N * 4],cnt = 0,tot = 0;
long long ans = 0;
inline int sch(long long x)
{
	int l = 1,r = cnt;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(x <= v[mid]) r = mid;
		else l = mid + 1;
	}
	return l;
}
struct UFS{
	int fa[N * 4];
	inline void init()
	{
		for(int i = 1;i <= cnt;i++) fa[i] = i;
	}
	inline int find(int x)
	{
		if(fa[x] == x) return x;
		return fa[x] = find(fa[x]);
	}
	inline void unionn(int x,int y)
	{
		x = find(x);y = find(y);
		fa[x] = y;
	}
}p;
inline void add(int x,int y,int z)
{
	++tot;
	e[tot].u = x;
	e[tot].v = y;
	e[tot].w = z;
}
inline bool cmp(Edge x,Edge y)
{
	return x.w < y.w;
}
signed main()
{
	cin>>n>>m;
	for(int i = 1;i <= n;i++)
	{
		cin>>s[i]>>t[i];
		v[++cnt] = s[i]; v[++cnt] = t[i];
	}
	s[++n] = inf; t[++n] = 1; v[++cnt] = s[n];v[++cnt] = t[n];
	sort(v + 1,v + cnt + 1);
	cnt = unique(v + 1,v + cnt + 1) - (v + 1);
	p.init();
	for(int i = 1;i <= n;i++)
	{
		s[i] = sch(s[i]);
		t[i] = sch(t[i]);
		++sum[s[i]];--sum[t[i]];
		p.unionn(s[i],t[i]);
	}
	for(int i = 1;i <= cnt - 1;i++)
	{
		sum[i] += sum[i - 1];
		if(sum[i] > 0) ans += sum[i] * (v[i + 1] - v[i]);
		if(sum[i]) p.unionn(i + 1,i);//i -> i + 1 or i + 1 -> i都要连边、连通块相同 
	}
	for(int i = 1;i <= cnt - 1;i++)
		if(p.find(i) != p.find(i + 1))
			add(p.find(i),p.find(i + 1),v[i + 1] - v[i]);
	sort(e + 1,e + tot + 1,cmp);
	for(int i = 1;i <= tot;i++)
	{
		if(p.find(e[i].u) == p.find(e[i].v)) continue;
		p.unionn(e[i].u,e[i].v);
		ans += e[i].w;
	}
	cout<<ans;
	return 0;
}

代码小细节：在这一段当中

for(int i = 1;i <= cnt - 1;i++)
{
	sum[i] += sum[i - 1];
	if(sum[i] > 0) ans += sum[i] * (v[i + 1] - v[i]);
	if(sum[i]) p.unionn(i + 1,i);//i -> i + 1 or i + 1 -> i都要连边、连通块相同 
}

\(sum_i > 0\)和\(sum_i\)两个条件是不一样的，因为\(if(sum_i)\)指的是\(sum_i\)只要不为零，无论正负都为\(true\)，这里的意思就是无论向左还是向右连边，\(i\)和\(i + 1\)都要联通。然而前面的一句就是只在向右连边的时候将边权计入答案，向左连时就是0。