UOJ

Luogu

分析

我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。

既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。

然而欧拉回路还需要连通，所以我们还要求个 MST 把它们连起来。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#include "railroad.h"
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

const int N=400000+10;
const int inf=0x3f3f3f3f;

int n,s[N],t[N],d[N];
int S[N],top=0;

int m=0;
struct edge { int u,v,w; } e[N];
bool operator <(edge a,edge b) { return a.w<b.w; }

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void merge(int x,int y) {
    x=find(x),y=find(y);
    if (x!=y) f[x]=y;
}

ll plan_roller_coaster(vector<int> s,vector<int> t) {
    n=s.size();
    S[++top]=-inf,S[++top]=inf;
    for (int i=0;i<n;++i) S[++top]=s[i],S[++top]=t[i];
    sort(S+1,S+top+1); top=unique(S+1,S+top+1)-S-1;
    for (int i=0;i<n;++i) s[i]=lower_bound(S+1,S+top+1,s[i])-S;
    for (int i=0;i<n;++i) t[i]=lower_bound(S+1,S+top+1,t[i])-S;
    --d[2],++d[top];
    for (int i=0;i<n;++i) ++d[s[i]+1],--d[t[i]+1];
    for (int i=1;i<=top;++i) d[i]+=d[i-1];
    for (int i=1;i<=top;++i) f[i]=i;
    for (int i=0;i<n;++i) merge(s[i],t[i]);
    ll ans=0;
    for (int i=2;i<=top;++i) {
        if (d[i]>0) ans+=1ll*d[i]*(S[i]-S[i-1]);
        if (d[i]) merge(i-1,i);
    }
    for (int i=2;i<=top-2;++i)
        if (find(i)!=find(i+1)) e[++m]=(edge){i,i+1,S[i+1]-S[i]};
    sort(e+1,e+m+1);
    for (int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (find(u)!=find(v)) merge(u,v),ans+=w;
    }
    return ans;
}