Liveddd's Blog

愛にできることはまだあるかい

P6168 [IOI2016] railroad

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 5 分钟

很智慧的欧拉回路的题目。

尝试转化为一个图论问题，我们直接建若干个点表示速度。连 $(\text{INF},1,0),(\max_i(s_i,t_i),\text{INF},0)$，而对应的每个车站连边 $(s_i,s_{i+1},0)$，中间我们需要加上若干 $(v,v+1,0)$ 和 $(v+1,v,1)$，使得其存在一条欧拉回路并且最短。

考虑如何求。我们称 $(s_i,t_i,0)$ 若满足 $s_i<t_i$ 表示从左边覆盖 $(s_i,t_i)$，从右边覆盖同理。我们发现最优情况下，存在边 $(v+1,v,1)$，当且仅当 从左边覆盖的边数 大于 从右边覆盖的边数。对于边 $(v,v+1,0)$ 同理。于是我们直接把这一部分的贡献加上即可。

但是此时我们只是将其划分为若干个子欧拉回路，仍然可能存在不连通的情况。意味着我们还需要连若干双向边使其联通，所以跑一遍最小生成树就好了。时间复杂度 $\mathcal O(n\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
using ll=long long;
const int N=5e5+10,INF=1e9+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Edge
{
    int u,v,w;
    bool operator<(const Edge &t)const{return w<t.w;}
}e[N];

int n,m,tot;
int s[N],t[N];
int c[N],sum[N];
int fa[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
inline void merge(int x,int y){x=get(x),y=get(y),fa[x]=y;}
int main()
{
    read(n,m);
    m=0;
    for(int i=1;i<=n;i++)read(s[i],t[i]),c[++m]=s[i],c[++m]=t[i];
    ++n;
    s[n]=INF,t[n]=1;
    c[++m]=INF,c[++m]=1;
    sort(c+1,c+1+m);
    m=unique(c+1,c+1+m)-c-1;
    for(int i=1;i<=m;i++)fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        s[i]=lower_bound(c+1,c+1+m,s[i])-c;
        t[i]=lower_bound(c+1,c+1+m,t[i])-c;
        sum[s[i]]++,sum[t[i]]--;
        merge(s[i],t[i]);
    }
    
    ll ans=0;
    for(int i=1;i<m;i++)
    {
        sum[i]+=sum[i-1];
        if(sum[i]>0)ans+=1ll*sum[i]*(c[i+1]-c[i]);
        if(sum[i])merge(i,i+1);
    }
    for(int i=1;i<m;i++)
        if(get(i)!=get(i+1))
            e[++tot]={i,i+1,c[i+1]-c[i]};
    sort(e+1,e+1+tot);
    for(int i=1;i<=tot;i++)
    {
        if(get(e[i].u)!=get(e[i].v))
            merge(e[i].u,e[i].v),ans+=e[i].w;
    }
    printf("%lld\n",ans);
    return 0;
}